卡迈克尔数 Carmichael Numbers（挑战程序设计竞赛）

我们把对任意的 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;
else
cout<<n<<" is normal."<<endl;
}
}

最后

以上就是可耐向日葵为你收集整理的卡迈克尔数 Carmichael Numbers（挑战程序设计竞赛）的全部内容，希望文章能够帮你解决卡迈克尔数 Carmichael Numbers（挑战程序设计竞赛）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。