POJ 1284 原根個數：歐拉函數 φ(p-1) 直接計算

問題描述

給定奇素數 p，求其原根（本原根）的個數。

數學結論

素數 p 的原根個數恰為 φ(p-1)，其中 φ 為歐拉函數。即 p-1 的質因數分解 p-1 = Π pᵢᵃⁱ，則 φ(p-1) = Π (pᵢᵃⁱ - pᵢᵃⁱ⁻¹) = (p-1) × Π (1 - 1/pᵢ)。

算法

1. 讀入 p
2. 計算 n = p - 1
3. 分解 n 的質因數，套用公式計算 φ(n)

完整代碼

#include 
using namespace std;

int main() {
    long long p;
    while (cin >> p) {
        long long n = p - 1;
        long long ans = n;
        for (long long i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                ans -= ans / i;  // ans *= (1 - 1/i)
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) ans -= ans / n;  // 剩餘大質因數
        cout << ans << '\n';
    }
    return 0;
}

複雜度分析

質因數分解 O(√n)，p ≤ 2³¹-1 時 √n ≤ 46340，極快。多測試用例總時間可忽略。

數學背景補充

• 原根定義：g 是模 p 的原根，當 g 的階為 p-1，即 g 的冪次遍歷 1..p-1
• 存在性：模 p（素數）總存在原根，個數為 φ(p-1)
• 推廣：模 m 存在原根當且僅當 m = 2, 4, pᵏ, 2pᵏ（p 為奇素數）

避坑指南

• 輸入以 EOF 結束，while(cin>>p)
• p 保證為奇素數，無需驗證
• 使用 long long 防溢出（p-1 可達 2³¹-2）
• 分解質因數時及時除盡，避免重複處理