zcmimi's blog

阶:

定义:

m>1\gcd(a,m)=1,那么使得a^r \equiv 1 \pmod m成立的最小的正整数r称为a对模m的阶,记为\delta_m(a),或ord_m a

定理:

  1. m>1gcd(a,m)=1,满足a^n\equiv 1 \pmod m,那么\delta_m(a)|n.显然

  2. \delta_m(a) | \varphi(m)

    证明:

    欧拉定理: a^{\varphi(m)}\equiv 1\pmod m

    \therefore \delta_m(a)\le \varphi(m)

    \therefore \delta_m(a) | \varphi(m)

  3. \gcd(a,m)=1,那么a^i\equiv a_j\pmod m,当且仅当i\equiv j\pmod{\delta_m a}

  4. \delta_m a=t,那么\displaystyle \delta_ma^u=\frac t{\gcd(t,u)}

  5. a^0,a^1,a^2,\dots,a^{\delta_m a -1}m两两不同余。

原根

定义

m是正整数,a是整数,

\delta_m(a)=\varphi(m),则称a为模m的一个原根

判断是否有原根

m有原根,那么m=2,4,p^k,2p^k(充要条件)(p为素数)

求原根

原根一般都很小,可以通过直接枚举然后判断是否是原根

求最小原根:

枚举g,使\gcd(g,m)=1,设p_1,p_2,\dots,p_k\varphi(m)的所有不同质因数,若gm的原根,那么\forall 1\le i \le k, g^{\frac{\varphi(m)}{p_i}} \not = 1

若一个数m存在原根,可以证明m的最小原根在m^{0.25}级别.

这个结论意味着,我们求所有的原根时,枚举最小原根花费的时间一般都是可以接受的.

求所有原根:

gm的一个原根,则集合S={g^i|1\le i\le \varphi(m),\gcd(i,\varphi(m))=1}m的所有原根.

因此,若m有原根,那么m\varphi(\varphi(m))个关于模m两两互不同余的原根

性质

  1. 素数都是原根

  2. 满足fft中单位根的性质,可以用于ntt(快速数论变换)

  3. gm的一个原根

    g^0,g^1,g^2,\dots,g^{\varphi(m)-1}构成模m的简化剩余系

例题

[SDOI2015]序列统计

原根将乘法转加法的应用

我们可以把序列中所有数变成原根的次幂,

那么序列中所有数的乘积就可以转化为他们的和

设这个和为sum

设生成函数:\displaystyle f(x)=\sum_{i=0}^m [i\in S]x^i

可以发现f(x)^n次数为sum的那一项的系数就是答案

使用快速幂+快速数论变换

#include<bits/stdc++.h>
const int N=3000010,P=1004535809,G=3,Gi=334845270;
int n,m,X,S,f[N],F[N],l,r[N],b[N],L;
void mod(int&x){if(x>=P)x-=P;}
void swap(int&x,int&y){x^=y,y^=x,x^=y;}
int pw(int x,int b,int p=P){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%p;
        b>>=1;x=1ll*x*x%p;
    }
    return res;
}
void ntt(int*A,int typ){
    for(int i=0;i<L;++i)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int len=1;len<L;len<<=1){
        int Wn=pw(~typ?G:Gi,(P-1)/(len<<1));
        for(int i=0;i<L;i+=len<<1){
            int w=1;
            for(int k=0;k<len;++k){
                int t=1ll*w*A[i+k+len]%P;
                mod(A[i+k+len]=A[i+k]-t+P);
                mod(A[i+k]+=t);
                w=1ll*w*Wn%P;
            }
        }
    }
    if(~typ)return;
    int inv=pw(L,P-2);
    for(int i=0;i<L;++i)
        A[i]=1ll*A[i]*inv%P;
}
int a[N],tt;
int getg(){
    for(int i=2;i<=m-2;++i)
        if((m-1)%i==0)a[++tt]=i;
    for(int i=2;;++i){
        bool ff=1;
        for(int j=1;j<=tt;++j)
            if(pw(i,a[j],m)==1){ff=0;break;}
        if(ff)return i;
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&X,&S);
    for(int i=1,x=1,g=getg();i<=m-2;++i)
        b[x=1ll*x*g%m]=i;
    for(int i=1,t;i<=S;++i){
        scanf("%d",&t);
        if(t)F[b[t]]=1;
    }

    for(L=1;L<m;L<<=1,++l);
    L<<=1,++l;

    for(int i=0;i<L;++i)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    f[0]=1;
    while(n){
        ntt(F,1);
        if(n&1){
            ntt(f,1);
            for(int i=0;i<L;++i)
                f[i]=1ll*f[i]*F[i]%P;
            ntt(f,-1);
            for(int i=L-1;i>=m-1;--i)
                mod(f[i-m+1]+=f[i]),f[i]=0;
        }
        n>>=1;
        for(int i=0;i<L;++i)
            F[i]=1ll*F[i]*F[i]%P;
        ntt(F,-1);
        for(int i=L-1;i>=m-1;--i)
            mod(F[i-m+1]+=F[i]),F[i]=0;
    }
    printf("%d\n",f[b[X]]);
}

ZOJ 3998 Yet Another Data Structure Problem

题意:

给一个序列A,要求支持以下操作:

  1. 区间乘

  2. 区间里所有数都变成自己的k次幂

  3. 求区间乘积(mod 10000000007)

由于模数是质数,所以可以将每个数都变成原根的次幂

这样区间乘转化为区间加,区间次幂转化为区间乘,求区间乘积转化为求区间和

推荐:

https://zh.wikipedia.org/wiki/原根

http://tonyfang.is-programmer.com/posts/205326.html

原根
comment评论
Search
search