第一次集訓
目錄- 第一次集訓
- A - Goldbach's Conjecture
- 題目大意
- 解題思路
- 參考代碼
- B - Summation of Four Primes
- 題目大意
- 解題思路
- 參考代碼
- 總結
- C - Primed Subsequence
- 題目大意
- 解題思路
- 參考代碼
- D - Happy 2006
- 題目大意
- 解題思路
- 參考代碼
- A - Goldbach's Conjecture
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.“
解題思路
-
如果 **n **< 8 則不存在答案
-
如果 **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 個數是多少
解題思路
由歐幾里得演算法
\[gcd(a,b)=gcd(a+b*t,b) \]得大于 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/265594.html
標籤：其他