这题属于简单题,本来不想写进博客,但看了别人的优代码,真没想到那种方法,比较好。我用的快速幂然后开始遍历,时间可想而知。。。
代码(本人):
#include<stdio.h> int pow(int b,int m)//快速幂 { int ans=1; while(b) { if(b%2) { ans=(m*ans)%1000; } b/=2; m=(m*m)%1000; } return ans; } int pss(int b,int n) { int ans=1; while(b) { if(b%2) { ans=n*ans; } b/=2; n=n*n; } return ans; } int main() { int T; long long m; int i,j,k,x,y,q; scanf("%d",&T); while(T--) { scanf("%lld",&m); if(m<1000)//让起点大于1000 { q=m; for(i=1;i<=35;i++) if(pss(i,q)>=1000) break; } else { q=m%1000; i=1; } for(j=i;j<1000;j++) { int f=0; for(k=i;k<j;k++) { x=pow(j,q); y=pow(k,q); if(x==y) { f=1; break; } } if(f==1) break; } printf("%d\n",j+k); } return 0; }
代码(优):
#include<stdio.h> int main() { long int n,k,i; scanf("%d",&n); while(n--) { scanf("%d",&k); long int a[1000]={0},t,flag=0; if(k>=1000) { k%=1000; a[k]++; flag=1; } for(t=k,i=2;;i++) { k=t*k; if(flag==1||k>=1000) { k%=1000; a[k]+=i; if(a[k]>i)//如果成立说明已经存过数 break; } } printf("%d\n",a[k]); } }