原根定义

先引入一个概念：阶。

设a和n是互素的整数，a≠0,n>0 使得a^x≡1（mod n），x的最小整数就是a模n的阶，而当x=phi（n）时，称a为n的原根。

对于求出原根的好处：可以利用 [1,n-1]->i 求出的所有 aⁱ (mod n)为一个[1,n-1]中的整数只出现一次的序列。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}

ll fpow(ll a,ll n,ll p)
{
    ll sum=1,base=a%p;
    while(n!=0)
    {
        if(n%2)sum=sum*base%p;
        base=base*base%p;
        n/=2;
    }
    return sum;
}

vector<ll> getPrimFac(ll n)
{
    vector<ll>fac;
    fac.clear();
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            fac.push_back(i);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)fac.push_back(n);
    return fac;
}

bool hasRoot(ll n)
{
    if(n==2||n==4)return true;
    if(n<=1||n%4==0)return false;
    ll num=0;
    while(n%2==0)n/=2;
    for(ll i=3;i*i<=n;i++)
    {
        if(n%i==0)
        {
            num++;
            while(n%i==0)n/=i;
        }
    }
    if(n>1)num++;
    if(num==1)return true;
    return false;
}

ll getPhi(ll n)
{
    ll ans=n;
    for(ll i=2;i*i<=n;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;
}

ll getRoot(ll n)
{
    if(!hasRoot(n))return -1;//不存在原根返回-1
    if(n==2)return 1;
    if(n==3)return 2;
    if(n==4)return 3;
    ll w=getPhi(n);
    vector<ll>fac=getPrimFac(w);
    for(ll i=2;i<w;i++)
    {
        if(gcd(i,n)!=1)continue;
        ll is=1;
        for(ll j=0;j<fac.size();j++)
        {
            if(fpow(i,w/fac[j],n)==1)is=0;
        }
        if(is)return i;
    }
    return -1;
}

int main()
{
    ll p;
    scanf("%lld",&p);
    printf("%lldn",getRoot(p));
    return 0;
}

模板求p的原根

原文链接: https://www.cnblogs.com/starve/p/12977181.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/351242

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

相关推荐