POJ 1284 - Primitive Roots (原根 + 欧拉函数)

ゞ浴缸里的玫瑰 2022-06-06 22:40 185阅读 0赞

题意：求一个数的[原根][Link 1]数；  
设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 + 0.5);
        int ans = n;
        for(int i = 2; i <= m; i++) if(n % i == 0) {
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        } 
        if(n > 1) ans = ans / n * (n - 1);
        return ans;
    }

**扩充**  
**1、**欧拉函数出了求原根的个数，还可以求**约数的个数**，由唯一分解定理可以把n分成

### n=pa11pa22pa33…pakk  n的任意正约数只能包含p1，p2，p3等素因数，对于n的某个素因子pi，它在所求约数中的指数可以是0，1，2，…，ai共ai\+1种情况，而且不同的素因子之间相互独立，根据乘法原理，n的正约数的个数为   ![这里写图片描述][8ad4b31c8701a18b94aed93e9d2f07082838fe7e.jpg]   这个式子也是和欧拉函数等价的  **2、小于n且与n<script type="math/tex" id="MathJax-Element-2588">n</script>互素的整数个数。   ![这里写图片描述][1008672-20170503125207086-2060438470.png]   这个式子也是欧拉函数。**  `#include<iostream> #include<cmath> #define MAXN 65540 using namespace std; int phi[MAXN]; int euler_phi(int n) { int m = (int)sqrt(n + 0.5); int ans = n; for(int i = 2; i <= m; i++) if(n % i == 0) { ans = ans / i * (i - 1); while(n % i == 0) n /= i; } if(n > 1) ans = ans / n * (n - 1); return ans; } int main() { int n; while(cin >> n) { cout << euler_phi(n-1) << endl; } return 0; }` ###

[Link 1]: https://baike.baidu.com/item/%E5%8E%9F%E6%A0%B9/8103534?fr=aladdin
[8ad4b31c8701a18b94aed93e9d2f07082838fe7e.jpg]: https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/s=316/sign=ca4b36d4d243ad4ba22e40c1b4035a89/8ad4b31c8701a18b94aed93e9d2f07082838fe7e.jpg
[1008672-20170503125207086-2060438470.png]: http://images2015.cnblogs.com/blog/1008672/201705/1008672-20170503125207086-2060438470.png