题意翻译

题目描述：如果对任意的 1 < x < n 都有 x^n≡x(mod n) 成立的合数n称为Carmichael Numbers .先给出一些整数n,请判断是否为Carmichael Numbers 。 输入格式：n (2<n<65000) ,输入以0结尾。 输出格式：参见样例

题目描述

PDF

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1： 复制 
1729
17
561
1109
431
0
输出样例#1： 复制 
The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.

思路：

此题要符合两个条件
① 该数不是素数
② 该数 x^n≡x(mod n)从2到n - 1均要成立

#include <iostream>
using namespace std;
typedef long long ll;
bool prime[65010] = {false};
ll getnum(ll a, ll b, ll c) {
	ll ans = 1;
	while (b > 0) {
		if (b & 1 == 1) ans = ans * a % c;
		a = a * a % c;
		b >>= 1;
	}
	return ans;
} 
void isprime() {
	for (int i = 2; i < 65000; i++) {
		if (prime[i] == true) continue;
		for (int j = 2; i * j < 65000; j++) prime[i * j] = true;
	}
}
int main() {
	int n;
	isprime();
	while (cin >> n && n) {
		if (prime[n] == false) {
			printf("%d is normal.\n", n);
			continue;
		}
		bool flag = true;
		for (int i = 2; i < n; i++) {
			if (getnum(i, n, n) != i) {
				flag = false;
				break;
			}
		}
		if (flag == true) printf("The number %d is a Carmichael number.\n", n);
		else printf("%d is normal.\n", n);
	}
	return 0;
}