-->Carmichael Numbers
Descriptions:
题目很长，基本没用，大致题意如下
给定一个数n，n是合数且对于任意的1 < a < n都有a的n次方模n等于a，这个数就是Carmichael Number.
输出The number n is a Carmichael number.
n是素数
输出
n is normal.
Input
多组输入，第一行给一个n （2 < n < 65000) 。n = 0 表示输入结束并不需要处理
Output
对每组输入，输出它是不是卡迈克尔数，参考样例。
Sample Input
1729175611109431
Sample Output
The number 1729 is a Carmichael number.17 is normal.The number 561 is a Carmichael number.1109 is normal.431 is normal.
题目链接
可以先判定n是否为合数，是就接着判断。
由于i的n次方的值可能很大，因此次题可以采用快速幂取余，由于数值范围可能很大，因此可采用long long 类型。
由于i的n次方的值可能很大，因此次题可以采用快速幂取余，由于数值范围可能很大，因此可采用long long 类型。
AC代码
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 65000+10
using namespace std;
ll n;
ll mod;
int isprime[Maxn];//素数表
void eratos(int x)//求素数表，true为素数
{
for(int i=; i<=x; ++i)
isprime[i]=true;
isprime[]=isprime[]=false;
for(int i=; i<=x; ++i)
{
if(isprime[i])
{
int j=i+i;
while(j<=x)
{
isprime[j]=false;
j+=i;
}
}
}
}
ll qpow(ll a, ll n)//计算a^n % mod 快速幂
{
ll re = ;
while(n)
{
if(n & )//判断n的最后一位是否为1
re = (re * a) % mod;
n >>= ;//舍去n的最后一位
a = (a * a) % mod;//将a平方
}
return re % mod;
}
int main()
{
eratos(Maxn-);
while(cin>>n,n)
{
if(isprime[n])//是素数
cout << n << " is normal." << endl;
else//不是素数
{
int f=;
for(int i=; i<n; i++)//判断
{
mod=n;
ll t=qpow(i,n);
if(t!=i)
{
f=;
cout << n << " is normal." << endl;
break;
}
}
if(f)
cout << "The number " << n <<
" is a Carmichael number." << endl;
}
}
}