UVA-10006 Carmichael Numbers

​​題目傳送門​​

題目的意思就是給出n ，看它是否滿足下面兩個條件：

1. n是合數 。
2. 對于區間 [ 2 , n ) 的任意數a ，都使得 pow (a , n) % n == a成立。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=65000+10;
bool isprime[maxn];
int prime[maxn];
int tot,mod;
ll mypow(ll a,ll n)
{
  ll res=(ll)1;
  while(n)
  {
    if(n&1)
    res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}
void prime_match()
{
  tot=0;
  fill(isprime,isprime+maxn,true);
  isprime[0]=isprime[1]=false;
  for(int i=2;i<maxn;i++)
  {
    if(isprime[i])
    {
      prime[tot++]=i;
    }
    for(int j=0;j<tot&&i*prime[j]<maxn;j++)
    {
      isprime[i*prime[j]]=false;
      if(!(i%prime[j]))
      break;
    }
  }
}
int main()
{
  int n,i;
  prime_match();
  while(scanf("%d",&n)==1&&n)
  {
    if(isprime[n])
    {
      printf("%d is normal.\n",n);
      continue;
    }
    else
    {
      mod=n;
      for(i=2;i<n;i++)
      {
        int cnt=mypow(i,n);
        if(cnt!=i)
        break;
      }
      if(i>=n)
      {
        printf("The number %d is a Carmichael number.\n",n);
      }
      else
      {
        printf("%d is normal.\n",n);
      }
    }
  }
  return 0;
}