POJ 1284 - Primitive Roots (原根 + 歐拉函數)

題意：求一個數的原根數；

設g是P的一個原根，那麼 gi mod P 結果兩兩不同，

1 < g < P，0 < i < P（i最大取P-1）

就是說g是周遊出來的，次方數從小到大挨個判斷，如果結果兩兩不同的話，就是一個原根。

我們使用歐拉定理，x的原根數恰好為x-1的歐拉函數的值

//歐拉函數
int euler_phi(int n) {
    int m = (int)sqrt(n + );
    int ans = n;
    for(int i = ; i <= m; i++) if(n % i == ) {
        ans = ans / i * (i - );
        while(n % i == ) n /= i;
    } 
    if(n > ) ans = ans / n * (n - );
    return ans;
}
           

擴充

1、歐拉函數出了求原根的個數，還可以求約數的個數，由唯一分解定理可以把 n 分成

n= pa11 pa22 pa33 … pakk

n 的任意正約數隻能包含p1， p2 ， p3 等素因數，對于 n 的某個素因子pi，它在所求約數中的指數可以是0，1，2， … ，ai共 ai+1 種情況，而且不同的素因子之間互相獨立，根據乘法原理， n 的正約數的個數為

這個式子也是和歐拉函數等價的

2、小于n且與 n <script type="math/tex" id="MathJax-Element-2588">n</script>互素的整數個數。

這個式子也是歐拉函數。

#include<iostream>
#include<cmath>
#define MAXN 65540

using namespace std;

int phi[MAXN];

int euler_phi(int n) {
    int m = (int)sqrt(n + );
    int ans = n;
    for(int i = ; i <= m; i++) if(n % i == ) {
        ans = ans / i * (i - );
        while(n % i == ) n /= i;
    } 
    if(n > ) ans = ans / n * (n - );
    return ans;
}

int main() {
    int n;
    while(cin >> n) {
        cout << euler_phi(n-) << endl;
    }
    return ;
}