Carmichael Numbers （快速幂）

　当今计算机科学的一个重要的领域就是密码学。有些人甚至认为密码学是计算机科学中唯一重要的领域，没有密码学生命都没有意义。

　　阿尔瓦罗就是这样的一个人，它正在设计一个为西班牙杂烩菜饭加密的步骤。他在加密算法中应用了一些非常大的素数。然而确认一个非常大的数是不是素数并不是那么简单。一个费时的方法是用比这个数的平方根小的所有素数去除它，对于大整数来说，这样一定会毁掉这个杂烩菜饭的。

　　然而，一些很有信心耗时少的随机测试存在，其中一个就是费马测试。

　　在2和n-1之间随机选取一个数（n是我们要测试的数）。如果a ⁿ mod n = a 成立，n就可能是一个素数。

　　如果一个数通过费马测试很多次那么它就很可能是一个素数。

　　不幸的是，一些数不是素数但是它们依然能通过每一个比它小的数的费马测试。这些数被称作卡迈克尔数

　　这道题要求你写一个程序去测试给定的数是不是一个卡迈克尔数。

　　完成了这个任务的队伍有希望接受来自阿尔瓦罗的西班牙杂烩菜饭23333

多组输入，第一行给一个n （2 < n < 65000) 。n = 0 表示输入结束并不需要处理

对每组输入，输出它是不是卡迈克尔数，参考样例。

1729

561

1109

431

The number 1729 is a Carmichael number.

17 is normal.

The number 561 is a Carmichael number.

1109 is normal.

431 is normal.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

//尚不是特别大的数嘞！

//打表计算素数

int prime[65000];

void f()

{

	prime[0]=prime[1]=0;

	for(int i=2;i<65000;i++) prime[i]=1;

	for(int i=2;i<65000;i++)

		if(prime[i])

			for(int j=2*i;j<65000;j+=i)

				prime[j]=0;

}

ll qmod(ll a,ll b,ll m)//计算a^b MOD m

{

	ll ans=1;

	while(b)

	{

		if(b&1)  ans=(ans*a)%m;

		b>>=1;

		a=(a*a)%m;

	}

	return ans;

}

int tests(int n)

{

	for(int i=2;i<=n-1;i++)

		if(qmod(i,n,n)!=i) return 0;//点睛巨笔！

	return 1;

}

int main()

{

	f();

	int n;

	while(cin>>n&&n)

	{

		if(!prime[n] && tests(n))

			cout<<"The number "<<n<<" is a Carmichael number.\n";

		else cout<<n<<" is normal.\n";

	}

	return 0;

}

附录：https://vjudge.net/contest/310908#problem/A

巴特西

Carmichael Numbers （快速幂）

最新文章

热门文章