洛谷 UVA10006 Carmichael Numbers

题意翻译

题目描述：如果对任意的 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; }