正题

题目链接:https://www.luogu.com.cn/problem/P6091

题目大意

给出一个数\(p\)，求出它的所有在\([0,p]\)的原根。

解题思路

原根的定义，\(\delta_p(a)\)表示一个最小的\(n\)使得\(a^n\equiv1(mod\ p)\)，若\(gcd(a,p)=1\)且\(\delta_p(a)=\varphi(p)\)则\(a\)为\(p\)的一个原根。

两个个结论就是一个数有原根当且仅当它为\(2,4,p^a,2p^a\)（其中\(p\)为奇质数，\(a\in N^+\)）。还有若\(g\)表示最小正原根，那么其他原根可以被表示为\(g^k\% p(\ gcd(\varphi(p),k)=1\ )\)。

这两个结论在洛谷题解都有详细证明，这里就不多赘述了。

那么考虑如何求出最小正原根，因为原根的数量大约有\(\varphi(\varphi (p))\)个，所以密集度比较高，据说最小正原根约是\(O(n^{2.5})\)级别的。

所以考虑直接枚举，但是我们判定的时候肯定不能从\(1\sim \varphi(p)\)枚举来判断。

我们还需要用到一个结论就是如果对于\(gcd(a,p)=1\)且\(a^k\equiv 1(mod\ p)\)（也就是\(k\)是\(a\)模\(n\)的阶），那么有\(k|\varphi(p)\)。所以我们需要判定\(\varphi(p)\)的所有因子？看起来还是很大，但是我们显然有\(a^k\equiv 1(mod\ p)\)那么\(a^{kx}\equiv1(mod\ p)\)其中\(x\in N^+\)。所以我们只需要枚举\(\frac{\varphi(p)}{k}\)（其中\(k\)是\(\varphi(p)\)的质因子）即可，因为这些数包含了其他数的倍数。

时间复杂度\(O(n^{2.5}\log n+n\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define ll long long

using namespace std;

const ll N=1e6+10;

ll T,n,d,cnt,phi[N],pri[N];

bool v[N],rt[N];

vector<int> q;

void prime(){

    phi[1]=1;

    for(ll i=2;i<N;i++){

        if(!v[i])pri[++cnt]=i,phi[i]=i-1;

        for(ll j=1;j<=cnt&&i*pri[j]<N;j++){

            v[i*pri[j]]=1;

            if(i%pri[j]==0){

                phi[i*pri[j]]=phi[i]*pri[j];

                break;

            }

            phi[i*pri[j]]=phi[i]*phi[pri[j]];

        }

    }

    rt[2]=rt[4]=1;

    for(ll i=2;i<=cnt;i++){

        for(ll j=1;j<N;j*=pri[i])rt[j]=1;

        for(ll j=2;j<N;j*=pri[i])rt[j]=1;

    }

    return;

}

ll power(ll x,ll b,ll p){

    ll ans=1;

    while(b){

        if(b&1)ans=ans*x%p;

        x=x*x%p;b>>=1;

    }

    return ans;

}

ll gcd(ll x,ll y)

{return (!y)?x:gcd(y,x%y);}

void dec_phi(ll x){

    for(ll i=1;i<=cnt&&pri[i]*pri[i]<=x;i++)

        if(x%pri[i]==0){

            q.push_back(pri[i]);

            while(x%pri[i]==0)x/=pri[i];

        }

    if(x!=1)q.push_back(x);

    return;

}

bool check(ll x){

    if(power(x,phi[n],n)!=1)return 0;

    for(ll i=0;i<q.size();i++)

        if(power(x,phi[n]/q[i],n)==1)

            return 0;

    return 1;

}

signed main()

{

    scanf("%lld",&T);

    prime();

    while(T--){

        scanf("%lld%lld",&n,&d);q.clear();

        if(!rt[n]){printf("0\n\n");continue;}

        dec_phi(phi[n]);ll g=1;

        while(!check(g))g++;

        ll tmp=1;q.clear();

        for(ll i=1;i<=phi[n];i++){

            tmp=tmp*g%n;

            if(gcd(phi[n],i)==1)

                q.push_back(tmp);

        }

        printf("%lld\n",q.size());

        sort(q.begin(),q.end());

        for(ll i=1;i<=q.size()/d;i++)

            printf("%lld ",q[i*d-1]);

        putchar('\n');

    }

    return 0;

}

巴特西

P6091-[模板]原根

正题

题目大意

解题思路

code

最新文章

热门文章