【算法讲17：原根】阶 和 原根

【算法讲17：原根】

• S o u r c e \mathfrak{Source} Source
• 前置
• 整数的 ⌈ \lceil ⌈阶 ⌋ \rfloor ⌋ 和 ⌈ \lceil ⌈原根 ⌋ \rfloor ⌋
• 原根的存在性
• 模板题

S o u r c e \mathfrak{Source} Source

• 《初等数论及其应用》第六版第九章
  省略了很多帮助理解的例子和证明。浓缩了一下密集的知识点。

前置

• 乘性函数
  可以见博客的算法讲4、5、7

整数的 ⌈ \lceil ⌈阶 ⌋ \rfloor ⌋ 和 ⌈ \lceil ⌈原根 ⌋ \rfloor ⌋

整数的阶

• 定义：
  设 a 、 n a、n a、n 为互素的整数， a ≠ 0 a\ne 0 a​=0， n > 1 n>1 n>1，使得 a x ≡ 1 ( m o d n ) a^x\equiv 1\pmod n ax≡1(modn) 的最小正整数 x x x 称为 a a a 模 n n n 的阶。记作 o r d n a ord_na ordn​a
• 定理 9.1 9.1 9.1
  如果 a ⊥ n a\perp n a⊥n 且 a ≠ 0 a\ne 0 a​=0， n > 0 n>0 n>0，那么正整数 x x x 是 a x ≡ 1 ( m o d n ) a^x\equiv 1\pmod n ax≡1(modn) 的一个解当且仅当 o r d n a ∣ x ord_na|x ordn​a∣x
• 推论 9.1.1 9.1.1 9.1.1
  如果 a ⊥ n a\perp n a⊥n 且 a ≠ 0 a\ne 0 a​=0， n > 0 n>0 n>0，那么 o r d n a ∣ ϕ ( n ) ord_na|\phi(n) ordn​a∣ϕ(n)
  证明：根据欧拉定理得到 a ϕ ( n ) ≡ 1 ( m o d n ) a^{\phi(n)}\equiv 1\pmod n aϕ(n)≡1(modn)，根据定理 9.1 9.1 9.1得到。
  根据该推论，我们可以从 ϕ ( n ) \phi(n) ϕ(n)的所有因子中，去更快枚举阶。
• 定理 9.2 9.2 9.2
  如果 a ⊥ n a\perp n a⊥n 且 a ≠ 0 a\ne 0 a​=0， n > 0 n>0 n>0,那么 a i ≡ a j ( m o d n ) a^i\equiv a^j\pmod n ai≡aj(modn) 当且仅当 i ≡ j ( m o d o r d n a ) i\equiv j\pmod{ord_na} i≡j(modordn​a),其中 i , j i,j i,j 为非负整数。

原根

• 定义：
  如果 r ⊥ n r\perp n r⊥n ， n > 0 n>0 n>0，当 o r d n r = ϕ ( n ) ord_nr=\phi(n) ordn​r=ϕ(n) 时，称 r r r 是模 n n n 的原根 或者称 r r r 是 n n n 的原根。
• 定理 9.3 9.3 9.3
  如果 r ⊥ n r\perp n r⊥n ， n > 0 n>0 n>0，且 r r r 是 n n n 的原根，那么下列整数：
  r 1 , r 2 , ⋯   , r ϕ ( n ) r^1,r^2,\cdots,r^{\phi(n)} r1,r2,⋯,rϕ(n)
  构成了模 n n n 的既约剩余系。
  证明：根据定理 9.2 9.2 9.2易证。
• 定理 9.4 9.4 9.4
  如果 o r d n a = t ord_na=t ordn​a=t 并且 u u u 是一个正整数，那么有：
  o r d n ( a u ) = t / ( t , u ) ord_n(a^u)=t/(t,u) ordn​(au)=t/(t,u)
  证明：令 s = o r d n ( a u ) s=ord_n(a^u) s=ordn​(au)， v = ( t , u ) v=(t,u) v=(t,u)， t = t 1 v t=t_1v t=t1​v 且 u = u 1 v u=u_1v u=u1​v，得到 ( t 1 , u 1 ) = 1 (t_1,u_1)=1 (t1​,u1​)=1
  因为 t 1 = t / ( t , u ) t_1=t/(t,u) t1​=t/(t,u)，所以要证明 o r d n ( a u ) = t 1 ord_n(a^u)=t_1 ordn​(au)=t1​，所以先证明 ( a u ) t 1 ≡ 1 ( m o d n ) (a^u)^{t_1}\equiv 1\pmod n (au)t1​≡1(modn)。
  首先有
  ( a u ) t 1 = ( a u 1 v ) ( t / v ) = ( a t ) u 1 ≡ 1 ( m o d n ) (a^u)^{t_1}=(a^{u_1v})^{(t/v)}=(a^t)^{u_1}\equiv 1\pmod n (au)t1​=(au1​v)(t/v)=(at)u1​≡1(modn)
  这是因为 o r d n a = t ord_na=t ordn​a=t.由定理 9.1 9.1 9.1 得到 s ∣ t 1 s|t_1 s∣t1​
  另一方面，由
  ( a u ) s = a u s ≡ 1 ( m o d n ) (a^u)^s=a^{us}\equiv 1\pmod n (au)s=aus≡1(modn)
  得到 t ∣ u s t|us t∣us，因此 t 1 v ∣ u 1 v s t_1v|u_1vs t1​v∣u1​vs，于是 t 1 ∣ u 1 s t_1|u_1s t1​∣u1​s
  由于 ( t 1 , u 1 ) = 1 (t_1,u_1)=1 (t1​,u1​)=1 故 t 1 ∣ s t_1|s t1​∣s
  得到 s = t 1 = t / v = t / ( t , u ) s=t_1=t/v=t/(t,u) s=t1​=t/v=t/(t,u)
• 推论 9.4.1 9.4.1 9.4.1
  令 r r r 是模 n n n 的原根, n > 1 n>1 n>1，那么 r u r^u ru 是模 n n n 的一个原根当且仅当 ( u , φ ( m ) ) = 1 (u,\varphi(m))=1 (u,φ(m))=1
• 定理 9.5 9.5 9.5
  如果正整数 n n n 有一个原根，那么它一共有 φ ( φ ( n ) ) \varphi(\varphi(n)) φ(φ(n)) 个原根。
  证明：有 φ ( φ ( n ) ) \varphi(\varphi(n)) φ(φ(n)) 个这样的整数 u u u 满足 ( u , φ ( n ) ) = 1 (u,\varphi(n))=1 (u,φ(n))=1

原根的存在性

• 定理 9.15 9.15 9.15
  正整数 n ( n > 1 ) n(n>1) n(n>1)有原根当且仅当：
  n = 2 , 4 , p t , 2 p t n=2,4,p^t,2p^t n=2,4,pt,2pt
  其中 p p p 为奇素数且 t t t 是正整数。
  略去了一大片证明…

模板题

• 【模板】原根 | 洛谷 P6091
• 代码：
  时间复杂度： O ( n + T ( n 0.25 log ⁡ n × φ ( n ) log ⁡ φ ( n ) ) ) O(n+T(n^{0.25}\log n\times \varphi(n)\log \varphi(n))) O(n+T(n0.25logn×φ(n)logφ(n)))
  比较复杂…

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e6+50;

ll qpow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a%MOD;a=a*a%MOD;n>>=1;}return res;}
ll qpow(ll a,ll n,ll p){a%=p;ll res = 1LL;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}

int cnt;
bool vis[MAX];
int prime[MAX];
int phi[MAX];
bool hasrt[MAX];
void init(int n){
    cnt = 0;
    phi[1] = 1;
    for(int i = 2;i <= n;++i){
        if(!vis[i]){
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int 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] - 1);
            }else{
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
    hasrt[2] = hasrt[4] = true;
    for(int i = 2;i <= cnt;++i){
        ll tmp = prime[i];
        for(int j = 1;j <= n && tmp <= n;++j){
            hasrt[tmp] = true;
            if(tmp * 2 <= n)hasrt[tmp*2] = true;
            tmp = tmp * prime[i];
        }
    }
}
int prm[MAX];
int get_factors(int ph){
    int shu = 0;
    for(int i = 2;i*i<=ph;++i){
        if(ph % i == 0){
            prm[++shu] = i;
            while(ph % i == 0)ph /= i;
        }
    }
    if(ph > 1)prm[++shu] = ph;
    return shu;
}
bool check(int n,int g,int shu){
    if(qpow(g,phi[n],n) != 1)return false;
    for(int i = 1;i <= shu;++i){
        if(qpow(g,phi[n]/prm[i],n) == 1)return false;
    }
    return true;
}
int get_minrt(int n,int shu){
    for(int i = 1;i < n;++i){
        if(check(n,i,shu))return i;
    }
    return 0;
}
int ans[MAX];		/// 原根存在这里
void get_rt(int n,int rt){
    int tmp = 1;
    int shu = 0;
    for(int i = 1;i <= phi[n];++i){
        tmp = (ll)tmp * rt % n;
        if(__gcd(i,phi[n]) == 1){
            ans[++shu] = tmp;
        }
    }
    return ;
}
int main()
{
    init(1000000);
    int T;scanf("%d",&T);
    while(T--){
        int n,d;scanf("%d%d",&n,&d);
        if(!hasrt[n])printf("0\n\n");
        else{
            int res = phi[phi[n]];			/// 原根个数
            printf("%d\n",res);
            int shu = get_factors(phi[n]);
            int rt = get_minrt(n,shu);
            get_rt(n,rt);
            sort(ans+1,ans+1+res);
            for(int i = 1;i <= res/d;++i)
                printf("%d ",ans[i*d]);
            puts("");
        }
    }
    return 0;
}