Codeforces Round #324 (Div. 2) （快速判断素数模板）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces Round #324 (Div. 2) （快速判断素数模板），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5494字，纯文字阅读大概需要8分钟。
内容图文
蛋疼的比赛，当天忘了做了，做的模拟，太久没怎么做题了，然后C题这么简单的思路却一直卡到死，期间看了下D然后随便猜了下，暴力了下就过了。
A.找一个能被t整除的n位数，那么除了<=10以外，其他都可以用长度为n的10或100,1000 。。。 来往上加几个数而得到
#include <iostream> #include <stdio.h> #include <set> #include <algorithm> #include <string.h> usingnamespace std; int getwei(int x) { int sum=0; while(x) { sum++; x=x/10; } return sum; } int main() { int n,t; scanf("%d%d",&n,&t); if(n==1&&t==10) printf("-1"); elseif(n==1) { printf("%d",t); } else { int save; for(int i=10;i<99;i++) { if(i%t==0) { save=i; break; } } printf("%d",save); for(int i=2;i<n;i++) { printf("0"); } } return0; }
B.很好找的公式题，((27^n-7^n)%MOD+MOD)%MOD。n很不大所以直接暴力就行了。
#include <iostream> #include <stdio.h> #include <set> #include <algorithm> #include <string.h> usingnamespace std; #define MOD 1000000007 int main() { int n; scanf("%d",&n); longlong tmp=1; longlong tmp1=1; for(int i=0;i<n;i++) { tmp=tmp*27; tmp%=MOD; tmp1=tmp1*7; tmp1%=MOD; } tmp-=tmp1; tmp= (tmp%MOD+MOD)%MOD; cout<<tmp<<endl; return0; }
C.思维题，给出了长度为n的两个字符串a和b，要你找到一个c串使得c串分别与a串和b串的相同位置不同字符数恰好为t。可以这样想，如果在某个位置i上
如果a[i]==b[i]，那么可以贡献a和b相异值1或0
如果a[i]!=b[i],那么要么贡献串a的相异值为1，要么贡献b的相异值为1，要么同时贡献a和b的相异值1.
因为ab的相异值必须得相等，那么最小的相异值为：所有a[i]!=b[i]的个数和为sumaneb，(sumaneb+1)/2 。如果这个值>t那么必定无解，否则一定有解。
如果有解，因为a[i]==b[i]的情况是可控的，所以尽量先把这种情况全部加进来，如果这种情况全部算进来却还是小于t，那么就将a[i]!=b[i]的情况变成对a和b同时贡献的情况。
这样想其实挺复杂的，判断情况就要想，还得推公式一种情况弄个c串。
看了大神的代码立马觉得涨姿势，果真自己的思路太弱。大神的做法是先得出一个c串，使得和ab串完全不相等。然后从a[i]==b[i]的情况中一个一个加入相等的情况，如果全部设为相等后还是不够，那就冲a[i]!=b[i]中加入相等的，如果全部加完还是不行就输出-1.
用这种思路的大神开场不到20分钟就把这题A了。 。。
#include <iostream> usingnamespace std; int n, t; string a; string b; string c; int main() { cin >> n >> t; cin >> a >> b; int u = n; c = a; for (int i = 0; i < n; i++) { char x = ‘a‘; if (a[i] == x || b[i] == x) x = ‘b‘; if (a[i] == x || b[i] == x) x = ‘c‘; c[i] = x; } for (int i = 0; i < n; i++) { if (a[i] == b[i] && t != u) { c[i] = a[i]; u--; } } int z = 0; for (int i = 0; i < n; i++) { if (a[i] == b[i] || u == t) continue; if (z == 0) {c[i] = a[i]; z = 1;} else {c[i] = b[i]; u--; z = 0;} } if (u == t) cout << c << "\n"; else cout << "-1\n"; }
D.给出一个3到10^9的整数n，然后要求输出三个素数a,b,c使得a+b+c=n.
哥德巴赫猜想：任何一个大于二的偶数都可以分解为两个素数和。
我的猜想是任意一个<=10^9的偶数，都可以快速分拆为两个素数和。所以就可以将n-3快速拆分为两个素数。
其实我这种猜想风险还太大，我使用了rabbin算法快速的判断一个数是不是素数，但是这种方法虽然快但不是绝对正确的，有一定的失误率。
#include <iostream> #include <algorithm> #include <string.h> #include <stdio.h> usingnamespace std; #define S 100 typedef unsigned longlong LL; LL modular_multi(LL x,LL y,LL mo) { LL t; x%=mo; for(t=0;y;x=(x<<1)%mo,y>>=1) if (y&1) t=(t+x)%mo; return t; } LL modular_exp(LL num,LL t,LL mo) { LL ret=1,temp=num%mo; for(;t;t>>=1,temp=modular_multi(temp,temp,mo)) if (t&1) ret=modular_multi(ret,temp,mo); return ret; } bool miller_rabbin(LL n) { if (n==2)returntrue; if (n<2||!(n&1))returnfalse; int t=0; LL a,x,y,u=n-1; while((u&1)==0) t++,u>>=1; for(int i=0;i<S;i++) { a=rand()%(n-1)+1; x=modular_exp(a,u,n); for(int j=0;j<t;j++) { y=modular_multi(x,x,n); if (y==1&&x!=1&&x!=n-1) returnfalse; ///其中用到定理，如果对模n存在1的非平凡平方根，则n是合数。 ///如果一个数x满足方程x^2≡1 (mod n),但x不等于对模n来说1的两个‘平凡’平方根：1或-1，则x是对模n来说1的非平凡平方根 x=y; } if (x!=1)///根据费马小定理,若n是素数，有a^(n-1)≡1(mod n).因此n不可能是素数returnfalse; } returntrue; } int main() { int n; scanf("%d",&n); if(n==3) printf("1\n3"); elseif(n==5) printf("2\n2 3"); else { n-=3; for(int i=2;i<=n;i++) { if( miller_rabbin(i) ==true) { if(miller_rabbin(n-i) == true) { printf("3\n3 %d %d",i,n-i); break; } } } } return0; }
更确定的算法是，从n->1，先求出一个素数复杂度约等于10*sqrt(n)，然后剩下来的就暴力几乎不要时间。
E.这题想了挺久的。
其实问题可以简化为
1 2 3 4 ... n
a1 a2 a3 a4 .. an
标号为ai的要到i位置。 然后每次交换为|i-j|费用，ij为标号。
我的思路是既然现在交换是看之间相隔的距离了，那么我把一个长的交换分拆成小的交换可以换的更好的效果。具体做法是：
对于没一个ai，如果ai>i,这ai这个数需要往右移，将这个位置标记为>
如果ai<i,这ai这个数需要往左移，将这个位置标记为<
如果ai=i,这ai这个数已经到达位置，将这个位置标记为0
比如一组数据
1 2 3 4 5
3 4 5 1 2
就可以变为
1 2 3 4 5
> > > < <
接着对于没一个相邻或者中间只隔0的><的情况进行变换，知道所有的状态都为0
比如
3 4 5 1 2 （>>><<）->
3 4 1 5 2 (>><><)->
3 1 4 5 2 (><>><)->
1 3 4 5 2 (0>>><)->
1 3 4 2 5 (0>><0)->
1 3 2 4 5 (0><00)->
1 2 3 4 5 (00000)结束。
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <string.h> #include <math.h> usingnamespace std; #define N 2020 int f[N],tf[N]; int mylink[N]; int g[N]; int x[N*N],y[N*N]; int cnt; int main() { int ans=0; int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",tf+i); } for(int i=1;i<=n;i++) { scanf("%d",f+i); mylink[f[i]]=i; } for(int i=1;i<=n;i++) { tf[i]=mylink[ tf[i] ]; } for(int i=1;i<=n;i++) { if(tf[i]==i) g[i]=0; elseif(tf[i]>i) g[i]=1; else g[i]=-1; } while(1) { int flag=0; int pre=-1; int id=-1; for(int i=1;i<=n;i++) { if(g[i]==-1) { if(pre==1) { swap(tf[id],tf[i]); if(tf[id]>id) g[id]=1; elseif(tf[id]==id) g[id]=0; else g[id]=-1; if(tf[i]>i) g[i]=1; elseif(tf[i]==i) g[i]=0; else g[i]=-1; flag=1; x[cnt]=id; y[cnt]=i; ans+=i-id; cnt++; if(tf[i]==i) break; else { pre=1; id=i; } } else pre=-1; } elseif(g[i]==1) { pre=1; id=i; } } if(flag==0) break; } printf("%d\n",ans); printf("%d\n",cnt); for(int i=0;i<cnt;i++) printf("%d %d\n",x[i],y[i]); return0; }
原文：http://www.cnblogs.com/chenhuan001/p/4865526.html
内容总结
以上是互联网集市为您收集整理的Codeforces Round #324 (Div. 2) （快速判断素数模板）全部内容，希望文章能够帮你解决Codeforces Round #324 (Div. 2) （快速判断素数模板）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。