Problem Description
输入一个数，如果这个数不是素数同时满足(x^n)%n == x其中(x > 1, x < n)
思路：
正常就x^n的次方，求n次，会超时，所以用快速幂。
#include<bits/stdc++.h> using namespace std; long long Pow(long long x, long long n, long long mod)//快速幂 { long long sum = 1; while(n) { if(n & 1) sum = (sum * x) % mod; x = (x * x) % mod; n = n>>1; } return sum; } int main() { long long n; long long i; while(~scanf("%lld", &n) && n) { for(i = 2; i * i <= n; i++) { if(n % i == 0) break; } if(i * i <= n) {//不是素数 for(i = 2; i < n; i++) { if(Pow(i, n, n) == i); else break; } if(i != n) printf("%lld is normal.\n", n); else printf("The number %lld is a Carmichael number.\n", n); } else printf("%lld is normal.\n", n);//是素数 } }