第一次集训

A - Goldbach's Conjecture

In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:

Every even number greater than 4 can be
written as the sum of two odd prime numbers.

For example:

8 = 3 + 5. Both 3 and 5 are odd prime numbers.
20 = 3 + 17 = 7 + 13.
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.)
Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.

Input

The input will contain one or more test cases.
Each test case consists of one even integer n with 6 <= n < 1000000.
Input will be terminated by a value of 0 for n.

Output

For each test case, print one line of the form n = a + b, where a and b are odd primes. Numbers and operators should be separated by exactly one blank like in the sample output below. If there is more than one pair of odd primes adding up to n, choose the pair where the difference b - a is maximized. If there is no such pair, print a line saying "Goldbach's conjecture is wrong."

Sample Input

8
20
42
0

Sample Output

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

题目大意

给定一个 偶数 n (6 <= n < 1000000) 打印出两个质数 满足 两质数之和为 n

解题思路

哥德巴赫猜想：一个偶数可以用两个质数相加表示

先用质数筛筛出质数，再遍历每一个小于 n 的质数判断即可

参考代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll N = 10000010 ;
bool wpri[N];
ll pri[N],cnt;
void getprime(){//线性筛
	for(ll i=2;i<=N;i++){
		if(!wpri[i]) pri[++cnt]=i;
		for(ll j=1;pri[j]*i<N&&j<=cnt;j++){
			wpri[pri[j]*i]=1;
			if(i%pri[j]==0) break;
		}
	}
}
int main(){
	getprime();
	ll n;
	while(~scanf("%lld",&n),n){
		for(ll i=1;pri[i]<=n&&i<=cnt;i++)
			if(!wpri[n-pri[i]]){
				printf("%lld = %lld + %lld\n",n,pri[i],n-pri[i]);
				break;
			}
	}
	return 0;
}

B - Summation of Four Primes

Euler proved in one of his classic theorems that prime numbers are infinite in number. But can every number be expressed as a summation of four positive primes? I don’t know the answer. May be you can help!!! I want your solution to be very efficient as I have a 386 machine at home. But the time limit specified above is for a Pentium III 800 machine. The definition of prime number for this problem is “A prime number is a positive number which has exactly two distinct integer factors”. As for example 37 is prime as it has exactly two distinct integer factors 37 and 1.

Input

The input contains one integer number N (N<=10000000) in every line. This is the number you will have to express as a summation of four primes. Input is terminated by end of file.

Output

For each line of input there is one line of output, which contains four prime numbers according to the given condition. If the number cannot be expressed as a summation of four prime numbers print the line “Impossible.” in a single line. There can be multiple solutions. Any good solution will be accepted.

Sample Input:

24
36
46

Sample Output:

3 11 3 7
3 7 13 13
11 11 17 7

题目大意

给定一个正整数 n 问是否有一种正整数组合满足 由4个质数组成 且 4个数之和为n，若满足则输出组合否则输出”Impossible.“

解题思路

1. 如果 **n **< 8 则不存在答案

2. 如果 **n **>= 8 则存在答案

   哥德巴赫猜想：一个偶数可以用两个质数相加表示

若 n 为奇数，可使前两个元素为2，3，第三四个元素的和为偶数，根据哥德巴赫猜想可由两个质数组成，枚举每个素数判断即可

若 n 为偶数，可使前两个元素为2，2，第三四个元素的和为偶数，同上

参考代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll N = 10000010 ;
bool wpri[N];
ll pri[N],cnt;
void getprime(){//线性筛
	for(ll i=2;i<=N;i++){
		if(!wpri[i]) pri[++cnt]=i;
		for(ll j=1;pri[j]*i<N&&j<=cnt;j++){
			wpri[pri[j]*i]=1;
			if(i%pri[j]==0) break;
		}
	}
}
void getprime(int a){//埃式筛
	for(ll i=2;i<=N;i++)
		if(!wpri[i]){
			pri[++cnt]=i;
			for(int j=2;j*i<N;j++) wpri[i*j]=1;
		}
}
int main(){
	getprime();
	ll n;
	while(~scanf("%lld",&n)){
		if(n<8){printf("Impossible.\n");continue;}
		if(n&1){
			printf("2 3 ");
			n-=5;
		}else{
			printf("2 2 ");
			n-=4;
		}
		for(ll i=1;pri[i]<=n&&i<=cnt;i++)
			if(!wpri[n-pri[i]]){
				printf("%lld %lld\n",pri[i],n-pri[i]);
				break;
			}
	}
	return 0;
}

总结

数学知识：首先会质数筛法然后联系到哥德巴赫猜想即可

C - Primed Subsequence

Given a sequence of positive integers of length n, we define a primed subsequence as a consecutive
subsequence of length at least two that sums to a prime number greater than or equal to two.
For example, given the sequence:

3 5 6 3 8

There are two primed subsequences of length 2 (5 + 6 = 11 and 3 + 8 = 11), one primed subsequence
of length 3 (6 + 3 + 8 = 17), and one primed subsequence of length 4 (3 + 5 + 6 + 3 = 17).
Input
Input consists of a series of test cases. The first line consists of an integer t (1 < t < 21), the number
of test cases. Each test case consists of one line. The line begins with the integer n, 0 < n < 10001,
followed by n non-negative numbers less than 10000 comprising the sequence. You should note that
80% of the test cases will have at most 1000 numbers in the sequence.
Output
For each sequence, print the ‘Shortest primed subsequence is length x:’, where x is the length
of the shortest primed subsequence, followed by the shortest primed subsequence, separated by spaces.
If there are multiple such sequences, print the one that occurs first. If there are no such sequences,
print ‘This sequence is anti-primed.’.
Sample Input

3
5 3 5 6 3 8
5 6 4 5 4 12
21 15 17 16 32 28 22 26 30 34 29 31 20 24 18 33 35 25 27 23 19 21

Sample Output

Shortest primed subsequence is length 2: 5 6
Shortest primed subsequence is length 3: 4 5 4
This sequence is anti-primed.

题目大意

给定一个数列，询问其中是否存在一个 长度大于2 且数列内 每个数字之和为质数 的子数列

若存在则输出最短子数列长度和最短的符合题意的子数列 若有多个最短子数列则输出最先出现得子数列

若不存在则输出"This sequence is anti-primed."

解题思路

先用筛法筛出质数，再循环暴力判断满足题意的最小的子数列即可

参考代码

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 100010005 ;
bool wpri[N];
ll pri[N],cnt;
void getpri(){
	for(ll i=2;i<=N;i++){
		if(!wpri[i]) pri[++cnt]=i;
		for(ll j=1;pri[j]*i<N&&j<=cnt;j++){
			wpri[pri[j]*i]=1;
			if(i%pri[j]==0) break;
		}
	}
}
void solve(){
	int n,flen=1000000000;cin>>n;
	vector<int> v(n),ans;
	for(int i=0;i<n;i++) cin>>v[i];
	for(int i=0;i<n;i++){
		int sum=v[i];
		vector<int> now;
		now.push_back(v[i]);
		for(int j=i+1;j<n&&j-i+1<flen;j++){
			sum+=v[j];
			now.push_back(v[j]);
			if(!wpri[sum]){
				flen=j-i+1;
				ans=now;
				break;
			}
		}
	}
	if(ans.size()){
		cout<<"Shortest primed subsequence is length "<<flen<<": ";
		for(int i=0;i<ans.size();i++)
			if(i!=ans.size()-1) cout<<ans[i]<<" ";
			else cout<<ans[i];
	}else cout<<"This sequence is anti-primed.";
	cout<<"\n";
}
int main(){
	getpri();
	int t;cin>>t;while(t--) solve();
	return 0;
}

D - Happy 2006

Two positive integers are said to be relatively prime to each other if the Great Common Divisor (GCD) is 1. For instance, 1, 3, 5, 7, 9...are all relatively prime to 2006.

Now your job is easy: for the given integer m, find the K-th element which is relatively prime to m when these elements are sorted in ascending order.
Input

The input contains multiple test cases. For each test case, it contains two integers m (1 <= m <= 1000000), K (1 <= K <= 100000000).
Output

Output the K-th element in a single line.
Sample Input

2006 1
2006 2
2006 3

Sample Output

1
3
5

题目大意

给定两个数字 n，k 询问满足与 n 互质的第 k 个数是多少

解题思路

由欧几里得算法

得大于 n 的与 n 互质的数呈周期性，所以只用求出小于 n 的与 n 互质的数，再根据周期性求出大于 n 的数即可

参考代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1e6+10;
int pri[maxn]; 
int gcd(int a, int b){return b==0?a:gcd(b, a%b);}
int main(){
    int m, k, sum;
    while(cin>>m>>k){
        sum=1;
        for(int i = 1; i<=m; i++)
            if(gcd(i,m)==1) pri[sum++] = i;
        sum--;
        if(k%sum) cout<<(k/sum)*m+pri[k%sum] <<endl;
        else cout<<(k/sum-1)*m+pri[sum] <<endl;
    }
    return 0;
}