POJ 1284：素數模原根個數計算

題目

給定奇素數 p (3 ≤ p < 65536)，求模 p 的原根個數。原根定義：其冪次遍歷 {1,2,...,p-1}。例如模 7 的原根有 3,5。

數學原理

模素數 p 的原根個數等於 φ(p-1)，其中 φ 為歐拉函數。因為模 p 的乘法群是循環群，階為 p-1，生成元個數即 φ(p-1)。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXP = 70000;
int phi[MAXP], minDiv[MAXP];

void precompute() {
    for (int i = 1; i < MAXP; i++) minDiv[i] = i;
    for (int i = 2; i < MAXP; i++) {
        if (minDiv[i] == i) {
            if (1LL * i * i < MAXP)
                for (int j = i * i; j < MAXP; j += i)
                    if (minDiv[j] == j) minDiv[j] = i;
        }
    }
    phi[1] = 1;
    for (int i = 2; i < MAXP; i++) {
        int p = minDiv[i], j = i / p;
        phi[i] = phi[j];
        if (j % p) phi[i] *= (p - 1);
        else phi[i] *= p;
    }
}

int main() {
    precompute();
    int p;
    while (cin >> p) {
        cout << phi[p - 1] << '\n';
    }
    return 0;
}