UVA 10006 卡邁克爾數：快速冪判斷合數條件

定義與性質

卡邁克爾數是合數 n，滿足對所有 1 < x < n 有 x^n ≡ x (mod n)。等價於對所有與 n 互質的 x 有 x^(n-1) ≡ 1 (mod n)（費馬偽素數）。

判斷算法

1. 篩法預計算 65000 以內素數表。
2. 對輸入 n，若為素數直接輸出 "normal"。
3. 否則枚舉 x = 2..n-1，用快速冪計算 x^n % n，若存在 != x 則非卡邁克爾數。
4. 全部通過則輸出 "Carmichael number"。

快速冪實現

long long mod_pow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

完整代碼

#include <cstdio>
#include <cstring>
const int MAXN = 65000;
bool isPrime[MAXN];

int main() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i=2; i*i

優化註記
實際可只檢測與 n 互質的 x，但 n≤65000 直接全檢測也極快（65000 * log n 操作）。