A-prime Test Miller-Rabin 素数测试。不会搞,求不出最小质因子,数太大了。
B-Prime cuts
题意:给出n代表1-n之间的范围,m代表剪切素数的2*m或2*m-1的长度,从中间剪切,保证剩下的两端长度相同。
分析:素数筛选,找到在n范围素数的个数,即等到k。设剪切首的位置为pos,末尾位置为endpos。
根据题意:pos=n-1-endpos,
endpos-pos+1=2*m(2m-1)
pos=(k+2-2*m)/2;pos为整数,如果不能整除即取2*m-1,得pos=(k+2-2*m)/2+1;
B:
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std ; const int N=10005; int prime[N],p[N]; int index=0; void Getprime() { for(int i=4;i<=N;i+=2){ p[i]=1; } int n=(int)sqrt(N); for(int i=3;i<=n;i+=2){ if(!p[i]){ for(int j=i*i;j<=N;j+=2*i) p[j]=1; } } for(int i=1;i<=N;i++){ if(!p[i]) prime[index++]=i; } } int main() { int i,n,m,pos,endpos; Getprime(); while(scanf("%d %d",&n,&m)!=EOF){ bool flag=0; for(i=0;i<index;i++){ if(n<prime[i]){ flag=1; break; } else if(n==prime[i]){ break; } } if(flag) i--; int tmp=i+2-2*m; if(tmp&1) pos=(tmp+1)/2,endpos=pos+2*m-1; else pos=tmp/2,endpos=pos+2*m; printf("%d %d:",n,m); if(pos<=0){ for(int j=1;j<=i;j++){ printf(" %d",prime[j]); } printf("\n\n"); } else{ for(int j=pos;j<endpos;j++){ printf(" %d",prime[j]); } printf("\n\n"); } } return 0 ; }
C-Primary Arithmetic
题意:求两个数相加进位的次数。
模拟加法的水题!注意格式就行's'.
C:
#include<iostream> #include<cstdio> #include<cstring> using namespace std ; char st1[12],st2[12]; int add(char *st1,char *st2) { int i,i1,i2,tmp,carry; int ans=0; i1=strlen(st1)-1,i2=strlen(st2)-1; carry=0; for(;i1>=0&&i2>=0;--i1,--i2){ tmp=st1[i1]-'0'+st2[i2]-'0'+carry; carry=tmp/10; if(carry>0) ans++; } while(i1>=0){ tmp=st1[i1--]-'0'+carry; carry=tmp/10; if(carry>0) ans++; } while(i2>=0){ tmp=st2[i2--]-'0'+carry; carry=tmp/10; if(carry>0) ans++; } return ans; } int main() { int ans; while(scanf("%s %s",&st1,&st2),st1[0]!='0'||st2[0]!='0'){ ans=add(st1,st2); if(ans==0) puts("No carry operation."); else if(ans==1)printf("%d carry operation.\n",ans); else printf("%d carry operations.\n",ans); } return 0 ; }
E - Ones
题意:给出n不能被2或5整除的数,存在为位数全部1的数,输出它最短能被n整除的位数。
同余定理的大水题。
#include<iostream> #include<cstdio> #include<cstring> using namespace std ; int main() { int n,i,sum; while(~scanf("%d",&n)){ if(n%2==0||n%5==0) continue; sum=0; for(i=0;;i++){ sum=(sum*10+1)%n; if(sum==0){ printf("%d\n",i+1); break; } } } return 0 ; }
F-青蛙的约会
扩展欧几里得(线性同余方程)
#include<iostream> #include<cstdio> #include<cstring> typedef long long LL; using namespace std ; LL exgcd(LL a,LL b,LL &x,LL &y) { if(b==0){ x=1; y=0; return a; } LL d=exgcd(b,a%b,x,y); LL t=x-a/b*y; x=y; y=t; return d; } int main() { LL x1,x2,m,n,l; LL x,y,c,d; while(scanf("%lld %lld %lld %lld %lld",&x1,&x2,&m,&n,&l)!=EOF){ c=x1-x2; d=exgcd(n-m,l,x,y); if(c%d){ puts("Impossible"); continue; } l/=d,c/=d; LL Min=((x*c)%l+l)%l; printf("%lld\n",Min); } return 0 ; }
G-Relatives
题意:求前n个数与n互质的个数(欧拉函数)
离散数学有个欧拉函数公式:f(n)=n(1-1/p1)*(1-1/p2)*....(1-1/pn) 其中:n=(p1^q1)*(p2^q2)*...(pn^qn) pn代表该数的一个质因子。
G:
#include<iostream> #include<cstdio> #include<cstring> typedef long long LL; using namespace std ; LL eular(LL x) { LL ret=1; for(int i=2;i*i<=x;i++){ if(x%i==0){ ret*=i-1; x/=i; while(x%i==0){ x/=i; ret*=i; } } } if(x>1) ret*=x-1; return ret; } int main() { LL n; while(scanf("%lld",&n),n){ printf("%lld\n",eular(n)); } return 0 ; }
H-Prime Land
题意:由n=(p1^e1)*(p2^e2)*...(pn^en) 求n-1的质因子和相应的指数,给出是p1 e1 p2 e2....pn en,输出是n-1的数分解因子的形式,按因子从大到小排列。
分析:先求出n,再分解n-1,很基础的一道质因子分解题。
H:
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std ; struct node{ int x,y; }ans[500]; char st[1005]; int a[1005],e,cnt; void read_num(char *s) { char t[10]; int p=0,len=strlen(s); cnt=0; s[len]=' '; for(int i=0;i<=len;i++){ if(s[i]==' '){ t[p]='\0'; sscanf(t,"%d",&a[cnt++]); p=0; } else t[p++]=s[i]; } } void get_ans(int n) { e=0; for(int i=2;i*i<=n;i++){ if(n%i==0){ n/=i; ans[e].x=i; ans[e].y=1; while(n%i==0){ n/=i; ans[e].y++; } e++; } } if(n>1) ans[e].x=n,ans[e++].y=1; } int main() { int num; while(gets(st)){ if(st[0]=='0') break; read_num(st); num=1; for(int i=0;i<cnt;i+=2){ num*=(int)pow(a[i],a[i+1]); } get_ans(num-1); for(int i=e-1;i>=0;i--){ printf(i==e-1?"%d %d":" %d %d",ans[i].x,ans[i].y); } puts(""); } return 0 ; }
I-prime gap
题意:在所有的素数中,给出一个数,求在两个相邻素数中包含该数n的相邻长度。
分析:筛选素数,查找n在两个相邻素数的位置,输出他们的长度即差,如果n是素数,答案为零,因为没有存在连续相邻的数为素数。
I:
#include<iostream> #include<cstdio> #include<cstring> typedef long long LL; using namespace std ; const int N=2000000; LL prime[N]; bool vis[N]; int index=0; void Get_prime() { for(int i=2;i<=N;i++){ if(!vis[i]) prime[++index]=i; for(int j=1;j<=index&&prime[j]*i<=N;j++){ vis[prime[j]*i]=1; if(i%prime[j]==0) break; } } } int main() { LL n; Get_prime(); while(scanf("%lld",&n),n){ if(!vis[n]){ puts("0"); continue; } for(int i=1;i<=index;i++){ if(n<prime[i]){ printf("%lld\n",prime[i]-prime[i-1]); break; } } } return 0 ; }
J-prime path
题意:给出两个四位数的素数,从第一个素数变到第二个素数,且每次变的过程中也必须为素数,变一次只能修改一个数的位数,且首位不能修改为零。
分析:先筛选素数,然后进行BFS,按着位去搜就行了,还是很基础的BFS。
J:
#include<cstdio> #include<cmath> #include<queue> #include<cstring> using namespace std; const int N=10000; const int a[4]={1,10,100,1000}; int visit[N],prime[N]; void Getprime() { int i,j; for(i=4;i<=N;i+=2){ prime[i]=1; } int n=(int)sqrt(N); for(i=3;i<=n;i+=2){ if(prime[i]) continue; for(j=i*i;j<=N;j+=2*i) prime[j]=1; } } void prime_BFS(int k,int m) { queue<int>Q; Q.push(k); visit[k]=0; while(!Q.empty()) { int s=Q.front(); Q.pop(); if(s==m){ printf("%d\n",visit[s]); return ; } for(int i=0;i<4;i++) { for(int j=0;j<10;j++) { int x=s/(a[i]*10); int y=s%a[i]; int num=x*a[i]*10+j*a[i]+y; if(num>1000&&visit[num]==-1&&!prime[num]) { Q.push(num); visit[num]=visit[s]+1; } } } } puts("Impossible"); } int main() { int n,k,m; Getprime(); while(scanf("%d",&n)!=-1) while(n--) { memset(visit,-1,sizeof(visit)); scanf("%d %d",&k,&m); if(!prime[k]&&!prime[m]) prime_BFS(k,m); else puts("Impossible"); } return 0; }
总结:本次比赛题目还是很基础的,A题的个数还是不多,主要原因是读题的速度慢,理解能力差,对基础的算法虽了解但不牢固,平时还是要多训练阅读能力和写代码的能力。
两种线性筛选素数的模板和欧拉函数模板我都敲下来了,果断敲了四五遍,应该很实用的,部分由讲解。
欧拉函数与素数筛选。
#include<cstdio> #include<cstring> #include<cmath> using namespace std; //本程序分别用两种方法求欧拉函数和素数筛选,并最后用一个函数 const int N=1000000; //实现素数筛选和欧拉函数值,算法效率都非常高,都很有技巧。 //这些典型的算法很基础,在平时训练中要做到水到渠成! int prime[N],phi[N]; bool vis[N]; void Get_prime1() //算法思想:先一次性筛选偶数,用每个素数一次性筛选含有它的因子的合数。 { //此算法适宜:素数的标记。 int index=0; for(int i=4;i<=N;i+=2) vis[i]=1; int n=(int)sqrt(N); for(int i=3;i<=n;i+=2){ if(vis[i]) continue; for(int j=i*i;j<=N;j+=2*i) vis[j]=1; } for(int i=2;i<=N;i++){ if(!vis[i]) prime[++index]=i; } } void Get_prime2() //与上述的思路一样,但算法更精简。 { //算法适宜:存取素数。 int index=0; for(int i=2;i<=N;i++){ if(!vis[i]) prime[++index]=i; for(int j=1;j<=index&&prime[j]*i<=N;j++){ vis[i*prime[j]]=1; if(i%prime[j]==0) break; //i含有一个素因子就“没必再用”i的倍数去筛选素数了,因为可以用 } //更小的素因子筛选了,保证不重复筛选一个合数了。 } } void Get_phi()//算法思路:根据n=(p1^q1)*(p2^q2)*..(pn^qn)===>phi[n]=n*(1-1/p1)*(1-1/p2)..(1-pn). { //==>phi[n]=n*[(p1-1)/p1]*...[(pn-1)/pn] phi[1]=0; //==>phi[n]=phi[n]/pi*(pi-1) 且 n%pi=0. for(int i=2;i<=N;i++) phi[i]=i; for(int i=2;i<=N;i+=2) phi[i]/=2; //偶数必含2的因子,根据公式n*(1-1/2)*..=(n/2)*.....。 for(int i=3;i<=N;i+=2) if(phi[i]==i){ for(int j=i;j<=N;j+=i){ //素数i,搜索i的倍数,即含有该素因子的合数。 phi[j]=phi[j]/i*(i-1); //见算法思路。 } } } int eular(int n) //此算法思路还是很简单的,只适宜求单个欧拉函数值 { int ret=1; for(int i=2;i*i<=n;i++){ if(n%i==0){ n/=i; ret*=i-1; while(n%i==0){ n/=i; ret*=i; } } } if(n>1) ret*=n-1; return ret; } void prime_phi() //此算法非常有技巧,把素数和欧拉函数结合起来,实现两种功能。 { int index=0; for(int i=2;i<=N;i++){ if(!vis[i]){ prime[++index]=i; phi[i]=i-1; //素数与它前面n-1个都互质。 } for(int j=1;j<=index&&prime[j]*i<=N;j++){ vis[i*prime[j]]=1; if(i%prime[j]==0){ //i含有一个素因子就“没必再用”i的倍数去筛选素数了,因为可以用 phi[i*prime[j]]=phi[i]*prime[j]; //更小素因子去筛选,它的欧拉函数值,正好多phi[i]个。 break; //phi[i]*(prime[j]-1)+phi[i]=phi[i]*prime[j]; } else phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } void Test(int n) { for(int i=1;i<=n;i++){ printf("prime[%d]=%d phi[%d]=%d\n",i,prime[i],i,phi[i]); } printf("\n"); } int main() { int n; //Get_prime1(); //Get_phi(); //Get_prime2(); prime_phi(); while(scanf("%d",&n)!=EOF) Test(n); //eular(n); return 0; }