水题一发。无奈自己没有好好审清题意，另外快速幂居然写错了- =
快速幂在过程中修改a的值，但是我却计算成了在偶数时相乘，调试半天。看来还是咩有好好理解啊。
#include <iostream> #include <cstdio> #include <cstring> #include <set> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <bitset> using namespace std; // 大数，内存处理 #define INF 0x3f3f3f3f #define ll long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(b, -1, sizeof(b)) #define DEB(x, n) cout << (x) << " " << (n) << endl const double PI = acos(-1.0); #define CR printf("\n") // 调试用 template <class Type> void debug(Type a[], int len) { for(int i = 0; i < len ; i++) { cout << a[i] << " "; } cout << endl; } ll p; ll pow_mod(ll a, ll n) { ll ans = 1; a %= p; while(n) { if(n & 1) ans = ans * a % p; a = a * a % p; n >>= 1; } return ans; } // 3. const int maxn = 10000000 + 10; const int maxp = 700000; int vis[maxn]; int prime[maxp]; // 筛素数 void sieve(int n) { int m = (int) sqrt(n+0.5); memset(vis, 0, sizeof(vis)); for(int i = 2; i <= m;i ++) if(!vis[i]) for(int j = i*i; j <= n; j+=i) vis[j] = 1; } // 生成素数表 int gen_primes(int n) { sieve(n); int c = 0; for(int i = 2; i <= n; i++) if(!vis[i]) prime[c++] = i; return c; } int main() { #ifdef DEBUG // freopen("input", "r", stdin); //从input文件中读入 // freopen("output", "w", stdout); //输出到output文件 #endif ll n; const int bound = 65000+10; gen_primes(bound); while(scanf("%lld", &n) && n!= 0) { // p is mod p = n; if(!vis[n]) printf("%lld is normal.\n", n); else { bool find = 1; for(ll i = 2; i < n;i ++) if(pow_mod(i, n) != i) { find = 0; break; } if(find) printf("The number %lld is a Carmichael number.\n", n); else printf("%lld is normal.\n", n); } } return 0; }