題目大意：判斷一個數字n是不是Carmichael number，所謂Carmichael number，滿足兩個條件：是合數；對于任意a(2<=a<=n-1)，都有a^n mod n=a。
只需要預處理篩素數和了解快速冪取模即可。
以下是我的代碼：
#include<stdio.h>
#include<math.h>
const long maxn=65007;
bool isPrime[maxn];
void get_prime()
{
long Prime[maxn],tot;
for(long i=1;i<maxn;i++) isPrime[i]=true;
isPrime[1]=false;
tot=0;
for(long i=2;i<maxn;i++)
{
if(isPrime[i])
{
tot++;Prime[tot]=i;
}
for(long j=1;j<=tot&&i*Prime[j]<maxn;j++)
{
isPrime[i*Prime[j]]=false;
if(i%Prime[j]==0) break;
}
}
}
long mod(long a,long n,long b)
{
if(n==1) return a%b;
long ans=mod(a,n/2,b);
ans=(ans*ans)%b;
if(n%2==1) return ans*a%b;
return ans;
}
bool check(long n)
{
for(long i=2;i<=n-1;i++)
if(mod(i,n,n)!=i)
return false;
return true;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
long n;
get_prime();
while(scanf("%ld",&n)==1)
{
if(n==0) break;
if(!isPrime[n]&&check(n))
printf("The number %ld is a Carmichael number.\n",n);
else printf("%ld is normal.\n",n);
}
return 0;
}
posted on 2010-01-23 19:56
lee1r 閱讀(1009)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數學/數論