【模板】原根题解

0xyz · 2023-05-14 11:50:48 · 题解

我来讲一下我做这道题的思路，并且给出一个 O(Tn) 的算法。代码很短，不到 1.2kb，比其它题解简便很多。

我的这个做法充满人类智慧，只需要知道原根的定义、阶的定义以及知道一个原根之后怎么求别的原根即可。其他题解的复杂度证明几乎都是错的。看一下这个帖子。

我的原根学习笔记。以下主要讲本题解法。

假设我们只求一次（求 T\le 10 次其实差不多），这里我给出 3 种方法，循序渐进。

1.O(n\log^2 n) 解法

假设我们要求整数 n 的所有原根，

求出 n 的欧拉函数 \varphi(n)。
将 \varphi(n) 质因数分解。
依照定义，找到最小原根 g。如果找不到，那就无解。
找到其余原根，也就是 g 的 x 次方，其中 \gcd(\varphi(n),x)=1。
排序后输出。

分析一下时间复杂度以及实现细节。

步骤 1 最坏情况下要枚举到 \sqrt n，所以时间复杂度是 O(\sqrt n)。

步骤 2 最坏情况下要枚举到 \sqrt{\varphi(n)}，所以时间复杂度是 O(\sqrt{\varphi(n)})。

步骤 3 要枚举最小原根 i:1\to n，时间复杂度是 O(n)，并且枚举 \varphi(n) 的质因数 s，判断使用快速幂判断 i^{\frac{\varphi(n)}{s}} 是不是模 n 余 1，时间复杂度是 O(n\log^2 n)。

步骤 4 直接枚举 i:1\to\varphi(n)，判断 i 是不是与 \varphi(n) 互质，O(\log\varphi(n))，如果是的话将 g^i 加入答案集合。由于是按照顺序枚举，直接一边枚举一边乘就可以了，不用快速幂。时间复杂度 O(\varphi(n)\log \varphi(n))。

步骤 5 将答案集合排个序，由于有 \varphi(\varphi(n)) 个原根，所以这一步的时间复杂度是 O(\varphi(\varphi(n))\log \varphi(\varphi(n)))。

所以总时间复杂度是 O(n\log^2 n)。常数较小。

以下是代码，用 m 表示输入的数，n 代表 \varphi(m)。总长 923b。可能是最短解。

AC 记录，开了 O2 最慢点 1.53 s，总共 9.92 s。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,c,s[20],ans[1000010],n,g,k,ca,T;
inline ll ksm(ll a,ll b){
    ll r=1;
    while(b){if(b&1)r=r*a%m;a=a*a%m;b>>=1;}
    return r;
}
inline void pri(ll x){
    c=0;
    for(ll i=2;i*i<=x;i++)
        if(x%i==0){s[++c]=i;while(x%i==0)x/=i;}
    if(x>1)s[++c]=x;
}
inline ll phi(ll x){
    pri(x);
    for(ll i=1;i<=c;i++)x=x/s[i]*(s[i]-1);
    return x;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        ca=g=0;
        cin>>m>>k;
        pri(n=phi(m));
        for(ll i=1;i<m;i++)
            if(ksm(i,n)==1){
                bool fl=1;
                for(ll j=1;j<=c;j++)
                    if(ksm(i,n/s[j])==1)fl=0;
                if(fl){g=i;break;}
            }
        if(!g){cout<<"0\n\n";continue;}
        for(ll i=1,p=g;i<=n;i++,p=p*g%m)
            if(__gcd(i,n)==1)ans[++ca]=p;
        sort(ans+1,ans+ca+1);
        cout<<ca<<'\n';
        for(ll i=1;i<=ca/k;i++)cout<<ans[i*k]<<' ';
        cout<<'\n';
    } 
    return 0;
}

2.O(n\log n) 解法

我们发现复杂度瓶颈是步骤 3。注意到王元并没有证明任何数的原根是 O(n^{0.25}) 的，所以这么枚举，时间复杂度依然是 O(n\log^2 n)。

但是注意到原根比较密集，也就是如果 n 有原根，并且我们只要找到任意一个原根就可以了（不需要一定是最小的）。

然后我写出了如下代码，求解 \frac{\varphi(\varphi(n))}{n} 的最小值。之所以最后从 3 开始是因为 \frac{\varphi(\varphi(2))}{2}=0。然后我惊喜地发现在 i\in [3,1000009] 中，\frac{\varphi(\varphi(n))}{n} 最小大于 0.04。那就是说，在最坏情况下，在 [1,n-1] 中随机选择一个数，有足足 4\% 以上的概率是 n 的原根。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll _=1000010;
ll c=0,p[_],e[_],ans=0;
bitset<_>v;
double mn=1e6;
int main(){
    v.set();
    for(ll i=2;i<_;i++){
        if(v[i])p[++c]=i,e[i]=i-1;
        for(ll j=1;j<=c&&i*p[j]<_;j++){
            v[i*p[j]]=0;
            if(i%p[j])e[i*p[j]]=e[i]*(p[j]-1);
            else{e[i*p[j]]=e[i]*p[j];break;}
        }
    }
    for(ll i=3;i<_;i++)
        if(double(e[e[i]])/double(i)<mn){
            mn=double(e[e[i]])/double(i);
            ans=i;
        }
    printf("%.6f %lld\n",mn,ans);
    return 0;
}

那我们随机大概 200 次就几乎肯定能找到一个原根，因为此时依然找不到原根的概率小于 0.96^{200}，小于 0.0003。

所以此时步骤 3 时间复杂度变为 O(\log^2 n)，然后 200 不算大常数。

于是总复杂度变为 O(\varphi(n)\log\varphi(n))。之所以步骤 4 成为瓶颈是因为 n 和 \varphi(n) 同阶。事实上，当 n 是质数时，\varphi(n)=n-1。

所以我们可以将时间复杂度简化为 O(n\log n)。

AC 记录，可以看到运行时间显著减少，开了 O2 后最慢的点仅 1.01 s，总共 5.70 s。代码长度 945b。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,c,s[20],ans[1000010],n,g,k,ca,T;
inline ll ksm(ll a,ll b){
    ll r=1;
    while(b){if(b&1)r=r*a%m;a=a*a%m;b>>=1;}
    return r;
}
inline void pri(ll x){
    c=0;
    for(ll i=2;i*i<=x;i++)
        if(x%i==0){s[++c]=i;while(x%i==0)x/=i;}
    if(x>1)s[++c]=x;
}
inline ll phi(ll x){
    pri(x);
    for(ll i=1;i<=c;i++)x=x/s[i]*(s[i]-1);
    return x;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        ca=g=0;
        cin>>m>>k;
        pri(n=phi(m));
        for(ll i=1,r;i<=200;i++)
            if(ksm((r=rand()%(m-1)+1),n)==1){
                bool fl=1;
                for(ll j=1;j<=c;j++)
                    if(ksm(r,n/s[j])==1)fl=0;
                if(fl){g=r;break;}
            }
        if(!g){cout<<"0\n\n";continue;}
        for(ll i=1,p=g;i<=n;i++,p=p*g%m)
            if(__gcd(i,n)==1)ans[++ca]=p;
        sort(ans+1,ans+ca+1);
        cout<<ca<<'\n';
        for(ll i=1;i<=ca/k;i++)cout<<ans[i*k]<<' ';
        cout<<'\n';
    } 
    return 0;
}

3. O(n) 做法

我们发现此时步骤 0、1、2、3 都是线性或者亚线性，只有步骤 4、5 是 O(n\log n) 级别的，所以考虑优化步骤 4、5。

对于步骤 5，我们注意到所有的答案都在 [1,n-1]，所以可以不用快速排序，直接用桶排序实现。

对于步骤 4，我们发现它时间复杂度较大是因为要求 n 次 \gcd，每次的时间复杂度是 O(\log n) 的。

一种解决方案是快速 \gcd，也就是经过 O(n) 预处理后进行 O(1) 的 \gcd。但是这样码量和常数都很大，甚至在随机数据下比 O(\log n) 的 \gcd 还慢。

我们发现已经将 \varphi(n) 质因数分解在 s 数组里了，那么如果 \gcd(i,\varphi(n))\ne 1，那么一定有 s_j\mid \gcd(i,\varphi(n))，也就是 s_j\mid i。如果一个一个去枚举 s_j 的话是 O(n\log n) 的，于是我想到了欧拉筛。它适用于筛掉所有质数的大于 1 倍的倍数，而这里是要筛掉一些特定的质数（s 数组）的倍数。

我改进了一下，使得它在依然是线性的同时拥有这个功能。

注意代码中的 n 仍然是上述的 \varphi(n)。

for(ll i=1;i<=c;i++)
    for(ll j=1;j<s[i]&&s[i]*j<=n;j++)u[s[i]*j]=0;
for(ll i=1;i<=n;i++)
    for(ll j=1;j<=c&&s[j]<=i&&i*s[j]<=n;j++){
        u[i*s[j]]=0;
        if(i%s[j]==0)break;
    }

对于正确性的证明：第一部分解决了所有 s_i 乘上一个比它小的数的情况，第二部分解决了所有 s_j 乘上一个比它大的数的情况。
对于线性时间复杂度的证明：容易知道一个数在第一部分一定是被最大质数×其余部分筛掉，在第二部分一定是被最小质数×其余部分筛掉，所以在两个部分各至多被筛一次。所以时间复杂度 O(n)。

于是我们就解决了这道题的 O(n) 做法。代码仅 1.17 kb。

AC 记录，最慢的点仅 139 ms，总时间 793 ms，是 O(n\log n) 做法时间的 \frac{1}{7}。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll _=1000010;
ll m,c,s[20],ans[_],n,g,k,cp,ca,T;
bitset<_>u,v;
inline ll ksm(ll a,ll b){
    ll r=1;
    while(b){if(b&1)r=r*a%m;a=a*a%m;b>>=1;}
    return r;
}
inline void pri(ll x){
    c=0;
    for(ll i=2;i*i<=x;i++)
        if(x%i==0){s[++c]=i;while(x%i==0)x/=i;}
    if(x>1)s[++c]=x;
}
inline ll phi(ll x){
    pri(x);
    for(ll i=1;i<=c;i++)x=x/s[i]*(s[i]-1);
    return x;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        ca=g=0;u.set();v.reset();
        cin>>m>>k;
        pri(n=phi(m));
        for(ll i=1,r;i<=200;i++)
            if(ksm((r=rand()%(m-1)+1),n)==1){
                bool fl=1;
                for(ll j=1;j<=c;j++)
                    if(ksm(r,n/s[j])==1)fl=0;
                if(fl){g=r;break;}
            }
        if(!g){cout<<"0\n\n";continue;}
        for(ll i=1;i<=c;i++)
            for(ll j=1;j<s[i]&&s[i]*j<=n;j++)u[s[i]*j]=0;
        for(ll i=1;i<=n;i++)
            for(ll j=1;j<=c&&s[j]<=i&&i*s[j]<=n;j++){
                u[i*s[j]]=0;
                if(i%s[j]==0)break;
            }
        for(ll i=1,p=g;i<=n;i++,p=p*g%m)
            if(u[i])v[p]=1;
        for(ll i=1;i<=m;i++)
            if(v[i])ans[++ca]=i;
        cout<<ca<<'\n';
        for(ll i=1;i<=ca/k;i++)cout<<ans[i*k]<<' ';
        cout<<'\n';
    } 
    return 0;
}

三、总结

在这道题里，我将原来 O(n\log^2 n) 的代码优化到了 O(n)。而具体的运行时间也由 9.92 s 优化到了 793 ms，最大的点也由 1.53 s 优化到 139 ms，不足原来的 \frac{1}{11}。而在这之间，我并没有采用硬件级别的优化或者其它卡常的措施，仅仅是基于我对于算法的理解以及人类智慧，优化算法。所以我认为 OIer 在学算法的时候，不应该一知半解，只是背一下板子而已，而是应该要学得透彻，不仅要学高深的算法，也要会尽力运用较为基础的算法。比如这个随机化，就是一个比较基础的算法，但是可以大幅优化时间复杂度。将枚举改变为随机化可以将枚举次数从大于 \frac{n}{2} 锐减至 200 次。还有这个扩展欧拉筛，是我在欧拉筛的基础上创造出来的。这样遇到新颖的题目时才可以更容易想出来。

四、鸣谢

感谢出题人 ix35 提供题目。

感谢 codecode 的讲解。

感谢 jijidawang 提供论文链接。

感谢 chenxia25 提供随机化做法。

感谢管理员审核一篇这么长的题解。

【模板】原根 题解