UVA 10006 卡邁克爾數判定：數論入門與快速冪優化

題目大意

輸入整數 n (n < 65000)，判斷：
• 若 n 為質數 → 輸出 "n is normal."
• 若 n 為合數，且對所有 2 ≤ a < n 滿足 aⁿ ≡ a (mod n) → 輸出 "The number n is a Carmichael number."
• 否則 → "n is normal."

卡邁克爾數定義

合數 n 滿足對所有與 n 互質的 a 有 aⁿ⁻¹ ≡ 1 (mod n)，等價於題目條件 aⁿ ≡ a (mod n)（對所有 a）。著名例子：561, 1105, 1729...。

解法一：暴力枚舉 + 快速冪

預計算 65000 以內質數表（埃氏篩）。對每個合數 n，枚舉 a = 2..n-1，用快速冪計算 aⁿ mod n，若全部等於 a 則為卡邁克爾數。
時間複雜度 O(n log n)，n ≤ 65000 可通過。

解法二：利用唯一分解定理優化

合數 n 可分解為質因子乘積。若對所有質因子 p 滿足 aⁿ ≡ a (mod p)，則對 n 也成立。預計算每個數的最小質因子 pri[i]，動態規劃計算 gcd[i] = aⁱ mod n：
gcd[i] = gcd[pri[i]] * gcd[i/pri[i]] mod n（若 i 為合數），質數直接快速冪。
大幅減少快速冪調用次數。

完整 C++ 代碼（解法二）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 65000;
int prime[MAXN], pri[MAXN];
long long gcd_val[MAXN];
long long n;

void init_sieve() {
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i < MAXN; ++i) {
        if (!prime[i]) {
            for (int j = i+i; j < MAXN; j += i) {
                prime[j] = 1;
                if (!pri[j]) pri[j] = i; // 記錄最小質因子
            }
        }
    }
}

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

int main() {
    init_sieve();
    while (cin >> n, n) {
        if (!prime[n]) { cout << n << " is normal.\n"; continue; }
        // 預計算 a=2,3 的冪，快速排除明顯非卡邁克爾數
        if (mod_pow(2, n, n) != 2 || mod_pow(3, n, n) != 3) {
            cout << n << " is normal.\n"; continue;
        }
        bool carmichael = true;
        gcd_val[1] = 1;
        for (int i = 2; i < n; ++i) {
            if (prime[i]) { // 合數
                int p = pri[i];
                gcd_val[i] = gcd_val[p] * gcd_val[i/p] % n;
            } else { // 質數
                gcd_val[i] = mod_pow(i, n, n);
            }
            if (gcd_val[i] != i) { carmichael = false; break; }
        }
        if (carmichael) cout << "The number " << n << " is a Carmichael number.\n";
        else cout << n << " is normal.\n";
    }
    return 0;
}

關鍵點總結

• 埃氏篩預計算質數與最小質因子 O(N log log N)。
• 快速冪 O(log n) 計算模冪。
• 利用乘法同餘性質 (x·y)ⁿ ≡ xⁿ·yⁿ (mod n) 遞推合數冪值。
• 先測 a=2,3 快速過濾絕大多數非卡邁克爾數。