大致题意：
给定一个数n，n是合数且对于任意的1 < a < n都有a的n次方模n等于a，这个数就是Carmichael Number.
思路：
可以先判定n是否为合数，是就接着判断。
由于a的n次方的值可能很大，因此次题可以采用快速幂取余（poj1995），由于数值范围可能很大，因此可采用long long 类型。
参考代码：
#include <iostream>
using namespace std;
typedef long long ll;
int flag_prime(ll num) {
int flag = 1;
if (num == 1) {
return 0;
}
for (ll k = 2;k * k <= num;++k) {
if (num % k == 0) {
flag = 0;
break;
}
}
return flag;
}
ll quickmod(ll a,ll n) {
ll res = 1;
ll b = n;
a = a % n;
while (b > 0) {
if (b & 1) {
res = res * a % n;
}
b >>= 1;
a = a * a % n;
}
return res;
}
int main() {
ll a,n;
ll res;
int flag2;
while (cin >> n && n) {
int flag = flag_prime(n);
if (flag) {
cout << n << " is normal." << endl;
}
else {
flag2 = 1;
for (a = 2;a <= n-1;++a) {
res = quickmod(a,n);
if (res != a) {
cout << n << " is normal." << endl;
flag2 = 0;
break;
}
}
if (flag2 == 1) {
cout << "The number " << a <<
" is a Carmichael number." << endl;
}
}
}
return 0;
}
此题我没考虑到1既不是素数又不是合数，幸好此题n的范围为2~65000.
