快速幂加素数筛。
我有两个错误点：
1.代码：
for(int i = 2; i < n; i++) if(power(i, n) != i){ flag = false; break; }里面break一开始没写， T了。
2.快速幂我一开始是int，WA了，然后改成long long就AC了。
#include <bits/stdc++.h> using namespace std; #define N 65001 typedef long long ll; bool pri[N]; bool ans[N]; int prm[N / 10]; void prime() { int cnt = 0; pri[2] = true; for(int i = 3; i < N; i += 2) pri[i] = true; for(int i = 2; i < N; i++){ if(pri[i]){ prm[cnt++] = i; } for(int j = 0; j < cnt && prm[j] * i < N; j++){ pri[prm[j] * i] = false; if(i % prm[j] == 0) break; } } } ll power(ll a, int n) { ll ans = 1; const int mod = n; a %= mod; while(n) { if(n & 1) ans = (ans * a) % mod; a = (a * a) % mod; n >>= 1; } return ans; } bool judge(int n) { if(pri[n]) return false; bool flag = true; for(int i = 2; i < n; i++) if(power(i, n) != i){ flag = false; break; } return flag; } int main() { int n; fill(ans, ans + N, true); prime(); for(int i = 3; i < N; i++) ans[i] = judge(i); while(scanf("%d", &n) && n) { if(ans[n]) printf("The number %d is a Carmichael number.\n", n); else printf("%d is normal.\n", n); } return 0; }