第一次集訓(xùn)
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
題目大意
給定一個(gè) 偶數(shù) n (6 <= n < 1000000) 打印出兩個(gè)質(zhì)數(shù) 滿足 兩質(zhì)數(shù)之和為 n
解題思路
哥德巴赫猜想：一個(gè)偶數(shù)可以用兩個(gè)質(zhì)數(shù)相加表示
先用質(zhì)數(shù)篩篩出質(zhì)數(shù)，再遍歷每一個(gè)小于 n 的質(zhì)數(shù)判斷即可
參考代碼
#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;
}
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
題目大意
給定一個(gè)正整數(shù) n 問是否有一種正整數(shù)組合滿足 由4個(gè)質(zhì)數(shù)組成 且 4個(gè)數(shù)之和為n，若滿足則輸出組合否則輸出”Impossible.“
解題思路
-
如果 **n **< 8 則不存在答案
-
如果 **n **>= 8 則存在答案
哥德巴赫猜想：一個(gè)偶數(shù)可以用兩個(gè)質(zhì)數(shù)相加表示
若 n 為奇數(shù)，可使前兩個(gè)元素為2，3，第三四個(gè)元素的和為偶數(shù)，根據(jù)哥德巴赫猜想可由兩個(gè)質(zhì)數(shù)組成，枚舉每個(gè)素?cái)?shù)判斷即可
若 n 為偶數(shù)，可使前兩個(gè)元素為2，2，第三四個(gè)元素的和為偶數(shù)，同上
參考代碼
#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;
}
總結(jié)
數(shù)學(xué)知識(shí)：首先會(huì)質(zhì)數(shù)篩法然后聯(lián)系到哥德巴赫猜想即可
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.
題目大意
給定一個(gè)數(shù)列，詢問其中是否存在一個(gè) 長(zhǎng)度大于2 且數(shù)列內(nèi) 每個(gè)數(shù)字之和為質(zhì)數(shù) 的子數(shù)列
若存在則輸出最短子數(shù)列長(zhǎng)度和最短的符合題意的子數(shù)列 若有多個(gè)最短子數(shù)列則輸出最先出現(xiàn)得子數(shù)列
若不存在則輸出"This sequence is anti-primed."
解題思路
先用篩法篩出質(zhì)數(shù)，再循環(huán)暴力判斷滿足題意的最小的子數(shù)列即可
參考代碼
#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;
}
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
題目大意
給定兩個(gè)數(shù)字 n，k 詢問滿足與 n 互質(zhì)的第 k 個(gè)數(shù)是多少
解題思路
由歐幾里得算法
\[gcd(a,b)=gcd(a+b*t,b)
\] 得大于 n 的與 n 互質(zhì)的數(shù)呈周期性，所以只用求出小于 n 的與 n 互質(zhì)的數(shù)，再根據(jù)周期性求出大于 n 的數(shù)即可
參考代碼
#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;
}
|
