我们把对任意的 1<x<n 都有 x^n≡x 成立的合数 n 称为 Carmichael Number。
对于给定的整数n, 请判断它是不是 Carmichael Number。
输入
- 多组测试数据，每组测试数据占据一行，一个整数 n，当输入的 n=0 时表示结束（不用处理 n=0)
- 除最后一行外，2<n<65000
输出
- 每组测试数据输出一行
- 当 n 是
Carmichael Number时，输出The number {输入的整数n} is a Carmichael number. - 当 n 不是
Carmichael Number时，输出{输入的整数n} is normal.
样例 1
输入
1729 17 561 1109 431 0
输出
The number 1729 is a Carmichael number. 17 is normal. The number 561 is a Carmichael number. 1109 is normal. 431 is normal.
卡迈克尔数的定义是对于合数n，如果对于所有正整数b，b和n互素，都有同余式b^(n-1)≡ 1 (mod n)成立，则合数n为Carmichael数。
卡迈克尔数是合数，所以需要先判断n是否是素数。
an mod n=(a mod n)n mod n=a
#include<bits/stdc++.h>
using namespace std;int isprime(int n)
{for (int i = 2; i*i <= n; i++)if (n%i == 0)return 0;return 1;
}
long long quickPow(long long base,long long power,long long p)
{long long result=1;while(power>0){if(power%2==1){result=result*base%p;}power=power/2;base=base*base%p;}return result;
}int main()
{int n;while(cin>>n){if(n==0)break;int flag = 1;if(isprime(n))flag=0;for(int i=2;i<n;i++){if(quickPow(i,n,n)!=i){flag=0;// cout<<n<<" is normal."<<endl;// return 0;}}if(flag)cout<<"The number "<<n<<" is a Carmichael number."<<endl;elsecout<<n<<" is normal."<<endl;}
}