题解 P6091 【【模板】原根】

移步博客

阶

  要定义原根，先要引入数论中阶的概念。

阶的定义

  设 a,m\in\mathbb{N^+}，且 a\perp m，使 a^x\equiv 1\pmod m 成立的最小正整数 x，称为 a 模 m 的阶，记为 \text{ord}_ma。

阶的性质

  说明：描述阶的性质时，默认 a,m\in\mathbb{N^+}，且 a\bot m，即 \mathrm{ord}_m a 存在。
  性质1 a^n\equiv 1\pmod m 的充要条件为 \mathrm{ord}_ma|n。
  证明 设 \mathrm{ord}_ma=x。
  首先证明充分性。设 n=px，其中 p\in\mathbb{N^+}。则 a^n\equiv a^{px}\equiv1\pmod m；即 a^n\equiv 1\pmod m。
  接下来证明必要性。设 n=px+q，其中 p\in\mathbb{N^+} ，且 0\le q<x,q\in\mathbb N。则 a^n\equiv a^{px+q}\equiv a^q\equiv 1\pmod m，得到 a^q\equiv 1\pmod m，由于 x 是满足 a^x\equiv1\pmod m 的最小正整数，又 0\le q<x，所以 q=0，故 x\mid n。
  证毕。
  推论1 \mathrm{ord}_ma\mid\varphi(m)。
  证明  由欧拉定理，a^{\varphi(m)}\equiv1\pmod m，故 \mathrm{ord}_ma\mid\varphi(m)。
  性质2 设 b\in\mathbb N^+，若 a\equiv b\pmod m，则 \text{ord}_ma=\text{ord}_mb。
  证明  首先 a\equiv b\pmod m，可以设 b=a+km,k\in\mathbb Z。则 \gcd(b,m)=\gcd(a+km,m)，由欧几里得算法 \gcd(b,m)=\gcd(m,a)=1，故 b\bot m，所以 \mathrm{ord}_mb 存在。
  接下来用反证法证明 \text{ord}_ma=\text{ord}_mb。假设 \text{ord}_ma=x，\text{ord}_mb=y，且 x\ne y。则 a^x\equiv(b-km)^x\equiv1\pmod m，将 (b-km)^x 用二项式定理展开，得到 b^x\equiv1\pmod m。根据假设 \mathrm{ord}_mb=y，故 x>y。然而，b^y\equiv(a+km)^y\equiv1\pmod m，将 (a+km)^y 用二项式定理展开，得到 a^y\equiv1\pmod m；由于 \mathrm{ord}_ma=x，故 x<y，产生矛盾；所以，x=y，即 \text{ord}_ma=\text{ord}_mb。
  证毕。
  性质3 设 p,q\in\mathbb N，a^p\equiv a^q\pmod m 的充要条件为 p\equiv q\pmod {\text{ord}_ma}。
  证明 首先证明充分性。设 p=k_1\mathrm{ord}_ma+r，q=k_2\mathrm{ord}_ma+r，其中 k_1,k_2,r\in\mathbb N，且 0\le r<\mathrm{ord}_ma。则 a^p\equiv a^{k_1\mathrm{ord}_ma+r}\equiv a^r\pmod m，同理，a^q\equiv a^r\pmod m，故 a^p\equiv a^q\pmod m。充分性得证。
  接下来证明必要性。不妨设 p\ge q，则 a^{p-q}\equiv 1\pmod m。根据性质1，\text{ord}_a m\mid p-q，所以 p\equiv q\pmod {\text{ord}_ma}。必要性得证。
  证毕。
  性质4 令 \text{ord}_ma=x，则 1,a,a^2,\cdots,a^{x-1}，模 m 两两不同余。
  证明 下面用反证法证明。
  假设 \exists\ i,j\in\mathbb N 且 0\le j<i<x，使得 a^i\equiv a^j\pmod m。故 a^{i-j}\equiv1\pmod m，由阶的定义，i-j\ge x，与 0\le j<i<x 矛盾。故假设错误。
  证毕。
  性质5 设 b\in\mathbb N^+，若 ab\equiv1\pmod m，则 \text{ord}_ma=\text{ord}_mb。
  证明  令 \text{ord}_ma=x，\text{ord}_mb=y，则有 a^x\equiv1\pmod m，b^y\equiv 1\pmod m。
  a^xb^x\equiv b^x\equiv1\pmod m，由阶的定义 x\ge y。a^yb^y\equiv a^y\equiv 1，由阶的定义，x\le y。所以，x=y。
  证毕。
  性质6 令 x=\text{ord}_ma，有 t\in\mathbb N^+ 则 \text{ord}_ma^t=\frac{x}{\gcd(t,x)}。
  证明 令 \text{ord}_ma^t=k，根据阶的定义，有 a^{kt}\equiv1\pmod m。
  由性质1，x\mid kt，故 \frac{x}{\gcd(t,x)}\mid\frac{t}{\gcd(t,x)}k 。根据最大公约数的性质，\frac{x}{\gcd(t,x)}\bot\frac{t}{\gcd(t,x)}，所以 \frac{x}{\gcd(t,x)}\mid k。
  根据阶的定义，k 为满足 \frac{x}{\gcd(t,x)}\mid k 的最小正整数，故 k=\frac{x}{\gcd(t,x)}。
  证毕。
  性质7 设 w\in\mathbb N^+，若 w\mid m，则 \text{ord}_wa\mid \text{ord}_ma。
  证明 由阶的定义，a^{\mathrm{ord}_ma}\equiv1\pmod m；因此，a^{\mathrm{ord}_ma}=km+1，k\in\mathbb N。因为 w\mid m，所以 a^{\mathrm{ord}_ma}\equiv1\pmod w。根据性质1，\text{ord}_wa\mid \text{ord}_ma。
  证毕。
  性质8 设 n\in\mathbb N^+。若 m\bot n,a\bot n，则 \text{ord}_{mn}a=\text{lcm}(\text{ord}_{m}a,\text{ord}_{n}a)。
  证明 令 x=\text{ord}_{mn}a，y=\text{lcm}(\text{ord}_{m}a,\text{ord}_{n}a)。
  根据阶的定义，a^x\equiv1\pmod{mn}，于是有 a^x=kmn+1，k\in\mathbb M；故 a^x\equiv 1\pmod {m}，a^x\equiv 1\pmod {n}。由性质1， \text{ord}_ma\mid x 且 \text{ord}_na\mid x，故 \text{lcm}(\text{ord}_{m}a,\text{ord}_{n}a)\mid x，即 y\mid x。
  由最小公倍数的定义，有 \mathrm{ord}_{m}a\mid y\text{ord}_{n}a\mid y。根据性质1，有 a^y\equiv1\pmod m 且 a^y\equiv1\pmod n；令 a^y=k_1m+1=k_2n+1，k_1,k_2\in\mathbb N，即 k_1m=k_2n。因为 m\bot n，故 k_1=kn,k_2=km，k\in\mathbb N，所以 a^y\equiv1\pmod{mn}。再次根据性质1，有 \mathrm{ord}_{mn}a\mid y，即 x|y。
  综上所述，x=y，即 \text{ord}_{mn}a=\text{lcm}(\text{ord}_{m}a,\text{ord}_{n}a)。
  证毕。
  性质9 设 b\in\mathbb N^+，若 b\bot m 且 \mathrm{ord}_ma\bot \mathrm{ord}_mb，则 \mathrm{ord}_mab=\mathrm{ord}_ma\times \mathrm{ord}_mb 。
  证明 令 x=\mathrm{ord}_ma，y=\mathrm{ord}_mb，z=\mathrm{ord}_mab。由阶的定义，有 a^x\equiv1\pmod m，b^y\equiv1\pmod m，(ab)^z\equiv1\pmod m。
  由 (ab)^z\equiv1\pmod m，得 a^z\equiv1\pmod m 且 b^z\equiv 1\pmod m。根据性质1，x\mid z 且 y\mid z，故 \mathrm{lcm}(x,y)\mid z。因为 \mathrm{ord}_ma\bot \mathrm{ord}_mb，即 x\bot y；所以 \mathrm{lcm}(x,y)=xy，即 xy\mid z。
  因为 x=\mathrm{ord}_ma 且 y=\mathrm{ord}_mb，所以 (ab)^{xy}\equiv 1\pmod m。根据性质1，z\mid xy。
  综上所述，z=xy，即 \mathrm{ord}_mab=\mathrm{ord}_ma\times \mathrm{ord}_mb。
  证毕。

原根

原根的定义

  设 g,m\in\mathbb N^+，且 g\bot m；若 \mathrm{ord}_mg=\varphi(m)，则称 g 是模 m 的原根。

原根存在定理

  不加证明地给出：模 {\displaystyle m} 有原根的充要条件是 m=2,4,p^k,2p^k，其中 p 是奇素数，k 是任意正整数。

原根判定定理

  不加证明地给出：若 g 为模 m 的原根，则对于任意 \varphi(m) 的质因子 p，必有 g^{\frac{\varphi(m)}{p}}\not\equiv 1 \pmod m。

求所有原根

  定理 设 g 为模 m 的原根，则集合 S=\{g^{s} \mid 1 \leq s \leq \varphi(m),s\bot\varphi(m)\} 给出模 m 的全部原根。模 m 的原根有 \varphi(\varphi(m)) 个。
  略证 由原根的判定定理，对于任意 \varphi(m) 的质因子 p，有 g^{\frac{\varphi(m)}{p}}\not\equiv 1 \pmod m；因此，\left(g^s\right)^{\frac{\varphi(m)}{p}}\equiv \left(g^{\varphi(m)}\right)^{\frac{s}{p}}\pmod m。若 \gcd(s,\varphi(m))>1，则存在一个 p，使得 p\mid s；此时，\left(g^{\varphi(m)}\right)^{\frac{s}{p}}\equiv g^{k\varphi(m)}\pmod m，k\in\mathbb N^+；根据欧拉定理 g^{\varphi(m)}\equiv1\pmod m。因此，当且仅当 s\bot\varphi(m)，g^s 才为模 m 的原根。
  若 s>\varphi(m)，由扩展欧拉定理，则 g^s\equiv g^{s\bmod \varphi(m)}\pmod m，转化为 1\le s\le \varphi(m) 的问题。
  根据欧拉函数定义，满足条件 1\leq s \leq \varphi(m),s\bot\varphi(m) 的 s 有 \varphi(\varphi(m)) 个。根据阶的性质4，这 \varphi(\varphi(m)) 个原根模 m 两两不同余。
  可以证明，最小原根是不大于 \sqrt[4]{m} 级别的。因此，不妨枚举 [1,\sqrt[4]{m}] 的整数，得到最小原根 g，这样的时间是可以接受的；接着，再枚举 g^s 的指数 s，若 s 与 \varphi(m) 互质，则 g^s\bmod m 为一个原根。
下面就有了本题的代码

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#define ll long long
#define N 1000002
using namespace std;
int cnt;//质数个数
bool vis[N];//vis[i]=1表示i为合数
int prime[N>>1];//质数
int phi[N];//欧拉函数
vector<int>prime_factor;//质因子
vector<int>ans;//所有模n的原根
//-------------------------------------------------------
//欧拉筛线性得到欧拉函数
void get_phi(int n)
{
    phi[1]=1;
    int i,j;
    for(i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            phi[i]=i-1;
            prime[++cnt]=i;
        }
        for(j=1;j<=cnt&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
//-------------------------------------------------------
//-------------------------------------------------------
//快速幂
inline int qpow_mod(ll a,int b,int mod)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
//-------------------------------------------------------
//-------------------------------------------------------
//分解质因数
inline void divide(int x)
{
    int i;
    for(i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            prime_factor.push_back(i);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) prime_factor.push_back(x);
}
//-------------------------------------------------------
//-------------------------------------------------------
//利用原根存在定理
bool exist(int n)
{
    if(n==2||n==4) return 1;
    if(n%2==0) n/=2;//猜测为奇素数幂的二倍
    int i;
    //检验是否为奇素数的幂
    for(i=2;prime[i]<=n;i++)
    {
        if(n%prime[i]==0)
        {
            while(n%prime[i]==0) n/=prime[i];
            //若n存在原根
            //i为唯一质因子
            return n==1;
        }
    }
    return 0;
}
//-------------------------------------------------------
//-------------------------------------------------------
int main()
{
    get_phi(1000000);//预处理1~1000000的欧拉函数
    int _;
    for(cin>>_;_;_--)
    {
        int n,d;
        scanf("%d%d",&n,&d);
        //首先检验n是否存在原根
        if(exist(n))
        {
            prime_factor.clear();
            ans.clear();
            //对phi[n]分解质因数
            divide(phi[n]);
            int i,j;
            int g;
            //---------------------------------------------------------
            //找到最小原根g
            for(i=1;;i++)
            {
                bool is=1;
                if(__gcd(i,n)!=1) continue;//i不存在模n的阶
                for(j=0;j<prime_factor.size();j++)
                {
                    //--------------------------------------------------
                    //原根判定
                    //对phi[n]的所有质因子p
                    //i^(phi[n]/p)%n!=1;
                    if(qpow_mod(i,phi[n]/prime_factor[j],n)==1)
                    {
                        is=0;
                        break;
                    }
                    //--------------------------------------------------
                }
                if(is)//找到最小原根
                {
                    g=i;
                    break;
                }
            }
            //---------------------------------------------------------
            //---------------------------------------------------------
            //枚举指数s
            //若s与phi[n]互质
            //g^s为原根
            int s;
            ll power=1;
            for(s=1;ans.size()<phi[phi[n]];s++)
            {
                power=power*g%n;
                if(__gcd(phi[n],s)==1) ans.push_back(power);
            }
            sort(ans.begin(),ans.end());
            printf("%d\n",phi[phi[n]]);
            //---------------------------------------------------------
            for(i=d-1;i<phi[phi[n]]/d*d&&i<ans.size();i+=d) 
            {
                //if(i) putchar(' ');
                printf("%d ",ans[i]);
            }
            putchar('\n');
        }
        else puts("0\n");
    }
    return 0;
}