51nod 1135 原根（数论）

悠悠 2022-06-15 01:45 234阅读 0赞

题目链接：  
[原根例题][Link 1]

求模素数P原根的方法：对![这里写图片描述][20140210203757296]素因子分解，即![这里写图片描述][20140210205528765]是P−1的标准分解式，若恒有![这里写图片描述][20140210205811375]  
成立，则![这里写图片描述][20140210203021625]就是![这里写图片描述][20140210202159109]的原根。（对于合数求原根，只需把![这里写图片描述][20140212124321781]换成![这里写图片描述][20140212124434953]即可）。

代码：

#include<bits/stdc++.h> 
    using namespace std;
    int p[100010];
    int t = 0;
    //http://blog.csdn.net/acdreamers/article/details/8883285
    void divide(long long n)
    {
        for(int i = 2; i * i <= n; i++){
            if(n % i == 0){
                p[t ++] = i;
                while(n % i == 0) n /= i;
            }
        }
    }
    
    int solve(long long x,long long n,long long m)
    {
        long long res = 1;
        while(n > 0){
            if(n & 1) res = (res * x) % m;
            x = (x * x) % m;
            n >>= 1;
        }
        return res;
    }
    
    int main()
    {
        long long a;
        cin >> a;
        divide(a - 1);//求a-1所有的质因子 
        for(int i = 2; i < a; i++)
        {
            bool flag = false;
            for(int j = 0; j < t; j++)
            {
                if(solve(i,(a - 1) / p[j], a ) == 1)//判断是否是原根 
                {
                    flag = true;
                    break;
                }
            }
            if(!flag){
                cout << i << endl;
                break;
            }
        }
        return 0;
    }

[Link 1]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135
[20140210203757296]: https://img-blog.csdn.net/20140210203757296
[20140210205528765]: https://img-blog.csdn.net/20140210205528765
[20140210205811375]: /images/20220615/9b57a4217f984632b7d56c377c0202f6.png
[20140210203021625]: https://img-blog.csdn.net/20140210203021625
[20140210202159109]: https://img-blog.csdn.net/20140210202159109
[20140212124321781]: https://img-blog.csdn.net/20140212124321781
[20140212124434953]: /images/20220615/98421edf25a449428dc8a3b1802b9ef8.png