题目描述：
当今计算机科学的一个重要的领域就是密码学。有些人甚至认为密码学是计算机科学中唯一重要的领域，没有密码学生命都没有意义。
阿尔瓦罗就是这样的一个人，它正在设计一个为西班牙杂烩菜饭加密的步骤。他在加密算法中应用了一些非常大的素数。然而确认一个非常大的数是不是素数并不是那么简单。一个费时的方法是用比这个数的平方根小的所有素数去除它，对于大整数来说，这样一定会毁掉这个杂烩菜饭的。
然而，一些很有信心耗时少的随机测试存在，其中一个就是费马测试。
在2和n-1之间随机选取一个数（n是我们要测试的数）。如果 mod n = a 成立，n就可能是一个素数。
如果一个数通过费马测试很多次那么它就很可能是一个素数。
不幸的是，一些数不是素数但是它们依然能通过每一个比它小的数的费马测试。这些数被称作卡迈克尔数
这道题要求你写一个程序去测试给定的数是不是一个卡迈克尔数。
完成了这个任务的队伍有希望接受来自阿尔瓦罗的西班牙杂烩菜饭23333
Input
多组输入，第一行给一个n （2 < n < 65000) 。n = 0 表示输入结束并不需要处理
Output
对每组输入，输出它是不是卡迈克尔数，参考样例。
Sample Input
1729
17
561
1109
431
0
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.
解题报告：
1：首先明确一点，素数也能满足这个条件。根据题意应该先判断这个数是不是素数。
2：套用快速幂模板判断就行了。注意技巧和顺序，避免超时。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Pow(ll base, ll n, ll mod){
ll ans = 1;
while(n){
if(n&1)ans = ans*base%mod;
n >>= 1, base = base*base%mod;
}
return ans%mod;
}
inline ll isPrime(ll n){
if(n == 2 || n == 3)return 1;
if( (n == 1) || (n%6 != 1 && n%6 != 5) )return 0;
ll s = sqrt(n);
for(ll i=5; i<=s; i+=6)
if(n%i==0 || n%(i+2)==0)return 0;
return 1;
}
int main(){
ll n;
while(~scanf("%lld", &n) && n){
if(isPrime(n)){
printf("%lld is normal.\n", n);
continue;
}
ll flag = 1;
for(ll i=2; i<=n-1; ++i){
if(Pow(i, n, n) != i){
flag = -1;
break;
}
}
if(flag == -1)
printf("%lld is normal.\n", n);
else
printf("The number %lld is a Carmichael number.\n", n);
}
return 0;
}