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 ;
}