学步园

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=12&problem=947&mosmsg=Submission+received+with+ID+8768565

这个题目应该是数论中比较入门的题目了

因为数据量并不是很大，所以可以直接暴力的打出素数表，然后进行判断

不过在取mod的时候可以把线性的乘法改成二分取mod，提升速度，然后就是变量类型可以改成long

int是会WA的，其他的就没有啥好主意的了。

我的代码：

#include<stdio.h><br /> #include<math.h><br /> #include<string.h></p> <p>long prime[65005];<br /> long num;<br /> bool flag[65005];</p> <p>void init()<br /> {<br /> unsigned long i,j;<br /> memset(flag,0,sizeof(flag));<br /> flag[1]=true;<br /> for(i=2;i<65005;i++)<br /> {<br /> if(!flag[i])<br /> {<br /> prime[num++]=i;<br /> for(j=i*i;j<=65005;j=j+i)<br /> flag[j]=true;<br /> }<br /> }<br /> }</p> <p>long power(long a,long n,long m)<br /> {<br /> long t;<br /> if(n==0)<br /> return 1%m;<br /> if(n==1)<br /> return a%m;<br /> t=power(a,n/2,m);<br /> t=((t%m)*(t%m))%m;<br /> if((n&1)==1)<br /> t=((t%m)*(a%m))%m;<br /> return t;<br /> }</p> <p>bool judge(long n)<br /> {<br /> long i;<br /> for(i=2;i<=n-1;i++)<br /> if(power(i,n,n)!=i)<br /> return false;<br /> return true;<br /> }</p> <p>int main()<br /> {<br /> long n;<br /> init();<br /> while(scanf("%ld",&n)!=EOF)<br /> {<br /> if(n==0)<br /> break;<br /> if(!flag[n])<br /> {<br /> printf("%ld is normal./n",n);<br /> continue;<br /> }<br /> else<br /> {<br /> if(judge(n))<br /> printf("The number %ld is a Carmichael number./n",n);<br /> else<br /> printf("%ld is normal./n",n);<br /> }<br /> }<br /> return 0;<br /> }