https://vjudge.csgrandeur.cn/problem/UVA-10006
当今计算机科学的一个重要的领域就是密码学。有些人甚至认为密码学是计算机科学中唯一重要的领域,没有密码学生命都没有意义。
阿尔瓦罗就是这样的一个人,它正在设计一个为西班牙杂烩菜饭加密的步骤。他在加密算法中应用了一些非常大的素数。
然而确认一个非常大的数是不是素数并不是那么简单。一个费时的方法是用比这个数的平方根小的所有素数去除它,
对于大整数来说,这样一定会毁掉这个杂烩菜饭的。
然而,一些很有信心耗时少的随机测试存在,其中一个就是费马测试。
在2和n-1之间随机选取一个数(n是我们要测试的数)。如果a 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.
解答
题意是找出一些和素数性质类似,但是不是素数的卡米尔数。
对于一个数n, 如果2和n-1之间的数a(n是我们要测试的数)。a^n mod n = a 均成立,n就可能是一个素数。
如果n不是素数,他就是卡米尔数
那么我们先打表 记录数据范围内所有的素数,然后保证n在表里面,逐个检测2和n-1 是否符合a^n mod n = a .
就可以判断是不是卡米尔数了。 a^n使用快速幂计算。
代码如下
#include <iostream>
#include <unordered_set>
using namespace std;
int n;
unordered_set<int> ss;
const int N = 65010;
int primes[N], cnt;
bool st[N];
void get_primes(int t) {
for (int i = 2; i <= t; i++) {
if (!st[i]) {
primes[cnt++] = i;
ss.insert(i);
}
for (int j = 0; primes[j] <= t / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int quickmi(long long a, long long b, long long m) {
long long ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % m;
}
b >>= 1;
a = a * a % m;
}
return ans;
}
void solve() {
if (ss.count(n) != 0) {
cout << n << " is normal." << endl;
return;
}
for (int i = 2; i < n; i++) {
if (quickmi(i, n, n) != i) {
cout << n << " is normal." << endl;
return;
}
}
cout << "The number "<< n<< " is a Carmichael number." << endl;
return;
}
int main()
{
get_primes(N);
while (cin >> n) {
if (0 == n) break;
solve();
}
return 0;
}
标签:10006,int,number,一个,素数,Numbers,测试,习题,Carmichael
From: https://www.cnblogs.com/itdef/p/18114080