数论基础 练习
A - Bi-shoe and Phi-shoe（LightOJ - 1370）
這道題的題意是給隊員購買竹子，每一個隊員都有一個幸運數字，購買竹子的價格的歐拉值大于等于幸運數字。換一個說法就是找比給你的幸運數字大的最小的質數。數據范圍100000。先打個質數表。然后暴力加起來就ok了。
1 #include<iostream> 2 using namespace std; 3 int a[1000005]; 4 void oula(){ 5 memset(a,0,sizeof(a)); 6 for(int i=2;i*i<=1000004;i++){ 7 if(!a[i]){ 8 for(int j=i+i;j<=1000004;j+=i){ 9 a[j]=1; 10 } 11 } 12 } 13 } 14 int main(){ 15 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 16 oula(); 17 int t; 18 cin>>t; 19 int cas=0; 20 while(t--){ 21 int n; 22 cin>>n; 23 ll sum=0; 24 for(int i=0;i<n;i++) 25 { 26 int x; 27 cin>>x; 28 for(int j=x+1;;j++){ 29 if(!a[j]){ 30 sum+=j; 31 break; 32 } 33 } 34 } 35 cout<<"Case "<<++cas<<": "<<sum<<" Xukha"<<endl; 36 } 37 38 return 0; 39 } View Code?
C - Aladdin and the Flying Carpet
LightOJ - 1341 這道題的題意是給你兩個數，一個數是面積s，一個是邊長最小n為多少，求有多少組數滿足乘積等于面積s，邊長大于等于n。這個是數學的基本定理，先求出這個數有多少的約數，在判斷有多少組數滿足條件。 m=p1^e1*p2^e2*...*pn^en。則他的約數的個數為n=(e1+1)*(e2+1)*...(en+1)。知道這個后這道題就簡單了。求出總共的約數除于2為總共的組數，減去1~n-1 滿足條件的約數組數，得到答案。為了簡單，先把10^6次方的素數表打出來。 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll p[1000100], prim[1000100]; 5 int k = 0; 6 void find_prim() 7 { 8 k = 0; 9 for(ll i = 2; i <= 1000000; i++) 10 { 11 if(!p[i]) 12 { 13 prim[k++] = i; 14 for(ll j = i+i; j <=1000000; j+=i) 15 { 16 p[j] = 1; 17 } 18 } 19 } 20 } 21 ll cont(ll a) 22 { 23 ll s = 1; 24 if(a == 0) 25 { 26 return 0; 27 } 28 ll tt = 0; 29 ll i = 0; 30 while(prim[i] < a && i < k) 31 { 32 tt = 0; 33 if(a%prim[i] == 0) 34 { 35 while(a%prim[i] == 0) 36 { 37 a/=prim[i]; 38 tt++; 39 } 40 } 41 s *= tt+1; 42 i++; 43 } 44 if(a > 1) 45 { 46 s *= 1+1; 47 } 48 return s; 49 } 50 int main() 51 { 52 ll a, b; 53 int t; 54 int cas = 0; 55 find_prim(); 56 scanf("%d",&t); 57 while(t--) 58 { 59 scanf("%lld%lld",&a,&b); 60 int cnt = 0; 61 ll num = 0, ans; 62 if(b >= sqrt(a)) 63 ans = 0; 64 else 65 { 66 for(ll i = 1; i < b; i++) 67 { 68 if(a%i == 0) 69 { 70 cnt++; 71 } 72 } 73 num = cont(a)/2; 74 ans = num - cnt; 75 } 76 printf("Case %d: %lld\n",++cas,ans); 77 } 78 return 0; 79 } View Code?
D - Sigma Function
LightOJ - 1336 這道題的題意是給你一個n，然后求1~n中有多少個數滿足他的因子和為偶數。我們可以發現一個定理就是完全平方數的因子和為奇數。比如4的因子和為1+2+4=7，比如9的因子和1+3+9=13。然后我們又可以推測2*完全平方數的因子和也是奇數。比如8=2*4他的因子和為1+2+4+8=15，18=2*9，它的因子和為1+2+3+6+9+18=39。然后再一想完全平方數乘以其他數會不會滿足這個條件。比如3*4=12，12的因子和為1+2+3+4+6+12=28 3*9=27，27的因子和為1+3+9+27=40 我們就會發現乘以一個奇數可以相當于是加上了一個奇數所以因子和為偶數。乘以一個完全平方數又變成另一個完全平方數。所以因子和為奇數的個數就為sqrt(x)+sqrt(x/2);所以答案就為x-sqrt(x)-(sqrt(x/2); 1 #include<iostream> 2 using namespace std; 3 int main(){ 4 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 5 int t; 6 cin>>t; 7 int cas=0; 8 while(t--){ 9 ll x; 10 cin>>x; 11 ll ans=(int)sqrt(x)+(int)sqrt(x/2); 12 cout<<"Case "<<++cas<<": "<<x-ans<<endl; 13 } 14 return 0; 15 } View CodeE - Leading and Trailing
這道題求前n^k次方的前三位和后三位。后三位不用說直接跑快速冪取模，唯一的坑點是補0，如果最后三位為001也需要輸出001。重點在于前三位怎么求。最開始也不會，網上看了代碼。然后自己也推了一下公式，最后懂了。設p=log(n^k)->10^p=n^k->這個就會發現p的整數位數代表的是總的位數，而p的小數代表的就是每位數上的值。p=klogn,然后有一個東西叫做fmod(x,y)。這個函數能夠得到小數部分，然后這道題就可以解決了。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 #include <cstdlib> 7 #include <limits> 8 #include <queue> 9 #include <stack> 10 #include <vector> 11 #include <map> 12 13 using namespace std; 14 15 #define N 10005000 16 #define INF 0x3f3f3f3f 17 #define PI acos (-1.0) 18 #define EPS 1e-8 19 #define met(a, b) memset (a, b, sizeof (a)) 20 21 typedef long long LL; 22 23 int quickpow (int m, int n, int k) 24 { 25 int b = 1; 26 while (n > 0) 27 { 28 if (n & 1) 29 b = (b * m) % k; 30 n >>= 1; 31 m = (m * m) % k; 32 } 33 return b%k; 34 } 35 36 int main () 37 { 38 int t, flag = 1; 39 scanf ("%d", &t); 40 41 while (t--) 42 { 43 LL n, k; 44 scanf ("%lld %lld", &n, &k); 45 46 int first = pow (10.0, 2.0 + fmod (k*log10(n*1.0), 1)); 47 int last = quickpow (n%1000, k, 1000); 48 49 printf ("Case %d: %d %03d\n", flag++, first, last); 50 } 51 return 0; 52 } View CodeF - Goldbach`s Conjecture
LightOJ - 1259 這道題就是有一個證明任何一個偶數等于兩個質數的和。現在就是問你有多少組滿足條件。并且a<=b。然后數據是10^7次方。可以打表，先把素數表打出來，一個數組存素數，一個存所有的數。然后用n減去這個質數，判斷這個是否為質數，然后得到答案。代碼如下。 1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cctype> 5 #include<queue> 6 #include<cmath> 7 #include<string> 8 #include<map> 9 #include<stack> 10 #include<set> 11 #include<vector> 12 #include<iostream> 13 #include<algorithm> 14 #define INF 0x3f3f3f3f 15 #define ll long long 16 const int N=10000005; //18 17 const int MOD=1000; 18 using namespace std; 19 bool prime[N]; 20 int p[N/10],pn; 21 void get_prime(){ 22 pn=0; 23 memset(prime,false,sizeof(prime)); 24 prime[0]=prime[1]=true; 25 for(long long i=2;i<N;i++){ 26 if(!prime[i]){ 27 p[pn++]=i; 28 for(long long j=i*i;j<N;j+=i){ 29 prime[j]=true; 30 } 31 } 32 } 33 } 34 int main(){ 35 get_prime(); 36 int T,n,num=1,ans; 37 scanf("%d",&T); 38 while(T--){ 39 scanf("%d",&n); 40 ans=0; 41 for(int i=0;p[i]<=n/2;i++){ 42 if(prime[n-p[i]]==false) ans++; 43 } 44 printf("Case %d: %d\n",num++,ans); 45 } 46 return 0; 47 } View Code?
?
G - Harmonic Number (II)
LightOJ - 1245 這道題的題意是給你一個n，求出sum的值，sum為n/i的累加，i為1~n。可以看兩個例子，n為8時8 4 2 2 1 1 1 1? n為10時10 5 3 2 2 1 1 1 1 1。以10為例，n/1和n/2分別有10個和5個(商大于等于1和商大于等于2得個數)，又因為n/2部分的數與n/1重復。故n/1不重復的有n/1-n/2個。依次類推，可以將n縮小到sqrt（n）的范圍內，在sqrt（n）之外的數，可以發現每一個正好對應n/i（借鑒的大佬的）對sqrt（n)循環，（n/i-n/(i+1))*i表示的是大于sqrt（n）的數中有（n/i-n/(i+1))個i 比如n=10，i=1時 表示的是有5個1。然后我們就會知道答案就是(n/i-(n/(i+1))*i+n/i。有一個地方你會發現如果n是一個完全平方數比如9 9 4 3 2 1 1 1 1 1 i=3時 加了1*3 然后在n/i又加了一個3。這是發現3加了兩次所以需要判斷下n是否為完全平方數。if（m/sqrt(n)==sqrt(n))。最后得到答案。1 #include<iostream> 2 using namespace std; 3 int main(){ 4 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 5 int t; 6 cin>>t; 7 for(int i=1;i<=t;i++){ 8 ll m; 9 cin>>m; 10 int n=sqrt(m); 11 ll sum=0; 12 for(int i=1;i<=n;i++){ 13 sum+=(m/i-m/(i+1))*i+m/i; 14 } 15 if(m/n==n) 16 sum-=m/n; 17 cout<<"Case "<<i<<": "<<sum<<endl; 18 } 19 return 0; 20 } View Code
H - Pairs Forming LCM
這道題的題意是給你一個n，滿足題意的個數有多少，這道題也是唯一分解定理中的幾個基本定理。將n唯一分解得到n=p1^e1*p2^e2*...*pn^en。然后我們就會發現lcm(i,j)=n,那么i,j的質因子分解必須滿足max(iei,jei)=ei。然后我們就會發現，當i滿足ei時，j就有ei種選擇，同理j滿足，i也有ei種,然后iei=jei=ei時又有一種所以需要在加一。所以總共的個數為sum=(e1*2+1)*(e2*2+1)*...*(en*2+1)。又因為j大于等于i,所以ans=sum/2，又因為i=j=n時這一種情況，所以還需要加一。最后的答案為ans=sum/2+1。
?
?
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<algorithm> 5 #include<stdio.h> 6 #include<string.h> 7 #include<stdlib.h> 8 #include<math.h> 9 #include<algorithm> 10 #include<iostream> 11 #include<vector> 12 #include<queue> 13 14 using namespace std; 15 typedef long long LL; 16 #define N 10010001 17 #define ESP 1e-8 18 #define INF 0x3f3f3f3f 19 #define memset(a,b) memset(a,b,sizeof(a)) 20 21 LL prime[1000000], k; 22 bool vis[N]; 23 24 void Prime() 25 { 26 memset(vis, false); 27 k = 0; 28 for(int i=2; i<N; i++) 29 { 30 if(vis[i] == 0) 31 { 32 prime[k ++] = i; 33 for(int j= i+i; j<N; j+=i) 34 { 35 vis[j] = 1; 36 } 37 } 38 } 39 } 40 41 LL solve(LL n) 42 { 43 LL ans, sum; 44 ans = 0; 45 sum = 1; 46 for(int i=0; prime[i] * prime[i] <= n; i++) 47 { 48 if(n%prime[i] == 0) 49 { 50 ans=0; 51 while(n%prime[i] == 0) 52 { 53 ans ++; 54 n /= prime[i]; 55 } 56 sum *= (2*ans+1); 57 } 58 } 59 if(n>1) 60 sum *= (2*1 + 1); 61 return sum; 62 } 63 64 int main() 65 { 66 int T, t=1; 67 LL n; 68 Prime(); 69 scanf("%d", &T); 70 while(T --) 71 { 72 LL n; 73 scanf("%lld", &n); 74 75 LL sum = solve(n); 76 77 printf("Case %d: %lld\n", t++, sum/2+1); 78 } 79 return 0; 80 } View Code?
?
I - Harmonic Number
LightOJ - 1234 這道題題意很簡單，但是數據為10^8次方O(n)循環過去也會炸時間，這個就是這道題的坑點了。上面這個式子的結果時存在一個公式的，調和級數f(n) 約等于1/(2*n)+ln(n)+C,C是歐拉常數約等于0.57721566490153286060651209（發現歐拉這個人還真是無所不能），這個公式就是求上面式子的，但這是一個近似的結果，所以我們要對前好多項去直接用上面的式子進行打表，然后在對之后的項套公式（當n很大時，我們就認為f(n)的誤差可以忽略）(膜拜大佬，https://blog.csdn.net/DEEPWAVE98/article/details/80640755?utm_source=blogxgwz3）這個是真的沒有想到需要調和級數這東西！！！。1 #include<iostream> 2 using namespace std; 3 double a[1000005]; 4 double C=0.57721566490153286060651209;//調和級數 n很大的時候 ans=logn+c+/(2*n); 5 void Init(){ 6 memset(a,0,sizeof(a)); 7 a[1]=1.0; 8 for(int i=2;i<=1000000;i++){ 9 a[i]=a[i-1]+1/(i*1.0); 10 } 11 } 12 int main(){ 13 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 14 Init(); 15 int T, t=1; 16 cin>>T; 17 while(T --) 18 { 19 ll n; 20 cin>>n; 21 double ans; 22 if(n>1000000){ 23 ans=log(n)+C+1.0/(2*n); 24 } 25 else 26 ans=a[n]; 27 printf("Case %d: %.10f\n", t++, ans); 28 } 29 30 return 0; 31 } View Code
J - Mysterious Bacteria
LightOJ - 1220K - Large Division
LightOJ - 1214 這道題一看數據有點懵，大數，我不會呀。后面才發現第二個數是long long范圍內，我去，這不是秀我嗎，就是一個簡單題，數組模擬大數，每步取模。 1 #include<iostream> 2 using namespace std; 3 int main(){ 4 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 5 char s[205]; 6 ll n; 7 int t; 8 cin>>t; 9 int cas=0; 10 while(t--){ 11 cin>>s>>n; 12 if(n<0) 13 n=-n; 14 int t=strlen(s); 15 ll sum=0; 16 for(int i=0;i<t;i++){ 17 if(s[i]=='-') 18 continue; 19 sum=(sum*10+s[i]-'0')%n; 20 } 21 if(sum==0) 22 cout<<"Case "<<++cas<<": divisible"<<endl; 23 else 24 cout<<"Case "<<++cas<<": not divisible"<<endl; 25 } 26 27 return 0; 28 } View Code?
L - Fantasy of a Summation
LightOJ - 1213
這道題就是自己找規律，然后發現每個數出現的次數為n^(k-1)*k。然后將前n個數累加乘以n^(k-1)*k得到答案。
1 #include<iostream> 2 using namespace std; 3 int main(){ 4 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 5 ll n,k,m; 6 int t; 7 cin>>t; 8 int cas=0; 9 while(t--){ 10 cin>>n>>k>>m; 11 int x; 12 ll sum=0; 13 for(int i=0;i<n;i++){ 14 cin>>x; 15 sum+=x; 16 sum%=m; 17 } 18 ll ans1=qpow(n,k-1,m)*k; 19 cout<<"Case "<<++cas<<": "<<(ans1*sum)%m<<endl; 20 } 21 22 return 0; 23 } View CodeM - Help Hanzo
LightOJ - 1197
這道題是求兩個數直接的質數有多少。首先對于任意的一個數n,他的最小質因數不會超過sqrt(n),那么就可以用[2，sqrt(n)]區間去篩掉[a,n]區間的約數，剩下的都是質數了，就是模擬區間篩法。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1000005; 4 bool pri[N]; 5 int pri1[N]; 6 int sum=0; 7 long long l,r; 8 void Init(){ 9 memset(pri,true,sizeof(pri)); 10 pri[1]=pri[0]=false; 11 for(register int i=2;i<N;i++){ 12 if(pri[i]){ 13 pri1[sum++]=i; 14 for(register int j=0;j<sum&&i*pri1[j]<N;j++){ 15 pri[i*pri1[j]]=false; 16 if(!(i%pri1[j])) 17 break; 18 } 19 } 20 } 21 } 22 void Init1(){ 23 memset(pri,true,sizeof(pri)); 24 for(register long long i=0;i<sum;i++){ 25 long long b=l/pri1[i]; 26 while(b*pri1[i]<l||b<=1){ 27 b++; 28 } 29 for(register long long j=b*pri1[i];j<=r;j+=pri1[i]){ 30 if(j>=l){ 31 pri[j-l]=false; 32 } 33 } 34 if(l==1) 35 pri[0]=false; 36 } 37 } 38 int main(){ 39 Init(); 40 int t; 41 scanf("%d",&t); 42 int cas=0; 43 while(t--){ 44 scanf("%lld%lld",&l,&r); 45 Init1(); 46 long long ans=0; 47 for(int i=0;i<=r-l;i++){ 48 if(pri[i]) 49 ans++; 50 } 51 printf("Case %d: %lld\n",++cas,ans); 52 } 53 return 0; 54 } View CodeN - Trailing Zeroes (III)
LightOJ - 1138 這道題的題意是給與一個n,求出最小的一個數的階乘滿足末尾有n個0,這個就是一個定理，末尾0只與5有關，然后二分查找是否滿足給的數n。具體的定理看代碼。 1 #include<iostream> 2 using namespace std; 3 ll sum(ll n){ 4 ll ans=0; 5 while(n){ 6 ans+=n/5; 7 n/=5; 8 } 9 return ans; 10 } 11 int main(){ 12 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 13 int t; 14 cin>>t; 15 int cas=0; 16 while(t--){ 17 ll x; 18 cin>>x; 19 // cout<<x<<endl; 20 ll l=0,r=10000000000; 21 ll ans=0; 22 while(l<=r){ 23 ll mid=(l+r)>>1; 24 if(sum(mid)==x){ 25 ans=mid; 26 r=mid-1; 27 } 28 else if(sum(mid)>x){ 29 r=mid-1; 30 } 31 else{ 32 l=mid+1; 33 } 34 } 35 // cout<<ans<<endl; 36 if(ans){ 37 printf("Case %d: %lld\n",++cas,ans); 38 } 39 else 40 printf("Case %d: impossible\n",++cas); 41 } 42 43 return 0; 44 } View CodeO - GCD - Extreme (II)
這道題的題意是給與一個n,求sum=gcd(i,j)(1<=i<n,i+1<=j<=n)。我們假如gcd(i,j)=1,當i循環到2*i，j循環2*j時,gcd(i,j)=2。我們會發現gcd(k*i,k*j)=k。假如與x互質的有n對（?,x),那么（2*?,2*x)就有2*n對，當i,j循環到(k*?,k*x)就有k*n對，我們可以a[i]把每個數的貢獻值記錄下來，a[i]表示的是i和小于i的最大公約數之和。然后我們最后輸出的就是a[2]+a[3]+...+a[n]。對于找互質的值，可以通過歐拉函數求出。
1 #include<iostream> 2 using namespace std; 3 int p[4000005]; 4 ll ans[4000005]; 5 void Init(){ 6 memset(ans,0,sizeof(ans)); 7 for(int i=1;i<=4000000;i++){ 8 p[i]=i; 9 } 10 for(int i=2;i<=4000000;i++){ 11 if(p[i]==i){ 12 for(int j=i;j<=4000000;j+=i) 13 p[j]=p[j]/i*(i-1); 14 } 15 for(int j=1;j*i<=4000000;j++){ 16 ans[j*i]+=j*p[i]; 17 } 18 } 19 for(int i=1;i<=4000000;i++) 20 ans[i]+=ans[i-1]; 21 } 22 int main(){ 23 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 24 Init(); 25 int n; 26 while(cin>>n&&n){ 27 cout<<ans[n]<<endl; 28 } 29 return 0; 30 } View Code?
1 //XDDDDDDi 2 #include <iostream> 3 #include <string> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <sstream> 7 #include <iomanip> 8 #include <map> 9 #include <stack> 10 #include <deque> 11 #include <queue> 12 #include <vector> 13 #include <set> 14 #include <list> 15 #include <cstring> 16 #include <cctype> 17 #include <algorithm> 18 #include <iterator> 19 #include <cmath> 20 #include <bitset> 21 #include <ctime> 22 #include <fstream> 23 #include <limits.h> 24 #include <cassert> 25 #include <climits> 26 #include <complex> 27 #include <streambuf> 28 #include <typeinfo> 29 #include <new> 30 /* 31 #include <array> 32 #include <numeric> 33 #include <unordered_map> 34 #include <unordered_set> 35 #include <random> 36 #include <tuple> 37 */ 38 using namespace std; 39 40 #define PB push_back 41 #define MP make_pair 42 #define MT make_tuple 43 #define pii pair<int,int> 44 #define pdd pair<double,double> 45 #define F first 46 #define S second 47 #define mian main 48 #define ture true 49 50 #define MAXN 1000000+5 51 #define MOD 1000000007 52 #define PI (acos(-1.0)) 53 #define EPS 1e-6 54 #define MMT(s,a) memset(s, a, sizeof s) 55 #define GO(i,a,b) for(int i = (a); i < (b); ++i) 56 #define GOE(i,a,b) for(int i = (a); i <= (b); ++i) 57 #define OG(i,a,b) for(int i = (a); i > (b); --i) 58 #define OGE(i,a,b) for(int i = (a); i >= (b); --i) 59 typedef unsigned long long ull; 60 typedef long long ll; 61 typedef double db; 62 typedef long double ldb; 63 typedef stringstream sstm; 64 const int INF = 0x3f3f3f3f; 65 int fx[4][2] = {1,0,-1,0,0,1,0,-1}; 66 67 /* 68 template<typename T> 69 using maxHeap = priority_queue<T, vector<T>, less<T> >; 70 template<typename T> 71 using minHeap = priority_queue<T, vector<T>, greater<T> >; 72 */ 73 74 template<typename T> 75 inline T gcd(T a, T b){ return b==0 ? a : gcd(b,a%b); } 76 template<typename T> 77 inline T lowbit(T x){ return x&(-x); } 78 template<typename T> 79 inline bool mishu(T x){ return x>0?(x&(x-1))==0:false; } 80 inline char nc(){ static char buf[1000000], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1000000,stdin),p1 == p2) ? EOF : *p1++; } 81 #define nc getchar 82 template<typename T> 83 inline int read(T& sum){ char ch = nc(); if(ch == EOF || ch == -1) return 0; int tf = 0; sum = 0; while((ch < '0' || ch > '9') && (ch != '-')) ch = nc(); tf = ((ch == '-') && (ch = nc())); while(ch >= '0' && ch <= '9') sum = sum*10 + (ch-48), ch = nc(); (tf) && (sum = -sum); return 1; } 84 template<typename T> 85 inline void print(T k){ int num = 0,ch[20]; if(k == 0){ putchar('0'); return ; } (k<0)&&(putchar('-'),k = -k); while(k>0) ch[++num] = k%10, k /= 10; while(num) putchar(ch[num--]+48); } 86 /*math*/ 87 template<typename T1,typename T2, typename T3> 88 ll qmul(T1 a,T2 b,T3 p){ ll w = 0; while(b){ if(b&1) w = (w+a)%p; b>>=1; a = (a+a)%p; } return w; } 89 template<typename T1,typename T2, typename T3> 90 ll qpow(T1 a,T2 b,T3 p){ ll w = 1; while(b){ if(b&1) w = (qmul(w,a,p))%p; b>>=1; a = (qmul(a,a,p))%p;} return w; } 91 template<typename T> 92 ll exgcd(T a, T b, T& x, T& y){ if(b == 0){ x = 1, y = 0; return (ll)a; } ll r = exgcd(b,a%b,y,x); y -= a/b*x; return r;/*gcd*/ } 93 94 /* ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- */ 95 int a[1000005]; 96 void oula(){ 97 memset(a,0,sizeof(a)); 98 for(int i=2;i*i<=1000004;i++){ 99 if(!a[i]){ 100 for(int j=i+i;j<=1000004;j+=i){ 101 a[j]=1; 102 } 103 } 104 } 105 } 106 int main(){ 107 ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0); 108 oula(); 109 int t; 110 cin>>t; 111 int cas=0; 112 while(t--){ 113 int n; 114 cin>>n; 115 // cout<<a[2]<<endl; 116 ll sum=0; 117 for(int i=0;i<n;i++) 118 { 119 int x; 120 cin>>x; 121 for(int j=x+1;;j++){ 122 if(!a[j]){ 123 // cout<<j<<' '; 124 sum+=j; 125 break; 126 } 127 } 128 } 129 cout<<"Case "<<++cas<<": "<<sum<<" Xukha"<<endl; 130 } 131 132 return 0;轉載于:https://www.cnblogs.com/cxylsy/p/10146975.html
總結
- 上一篇： 用第三方插件做分页
- 下一篇： 【C/C++】知识点系统复习 （第一周）