题目链接：点击打开链接
题意：给一个数n，问这个数是不是Carmichael Numbers，Carmichael Numbers的定义为：一个数n如果不是素数且对于对于任意的 2=
#include #include #include #include #include #include #include #include #include #include #include #include #include #define maxn 65002 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 10000007 #define pp pair #define ull unsigned long long using namespace std; ll n; bool pri[maxn]; void init() { memset(pri, 1, sizeof(pri)); pri[0] = 0; pri[1] = 0; for (int i = 2; i * i <= maxn; i++) { if (pri[i]) { for (int j = i * i; j <= maxn; j += i) { pri[j] = 0; } } } } ll pow_mod(ll a, ll n, ll p) { if (n == 0) { return 1; } ll ans = pow_mod(a, n / 2, p); ans = ans * ans % p; if (n & 1) { ans = ans * a % p; } return ans; } void solve() { if (pri[n]) { printf("%d is normal.\n", n); return ; } for (ll i = 2; i < n; i++) { if (pow_mod(i, n, n) != i) { printf("%d is normal.\n", n); return ; } } printf("The number %d is a Carmichael number.\n", n); } int main() { init(); while (~scanf("%lld", &n) && n) { solve(); } return 0; }