同余方程整理

· · 个人记录

同余方程整理

1. 解线性一次同余方程

前置知识：gcd，逆元，exgcd

题目要求：给出 a、b、p，求关于 x 的同余方程 ax\equiv b\pmod{p} 的最小整数解。

对于这一类的同余方程，我们运用 exgcd（扩展欧几里得算法） 求解。

void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){
        d=a;
        x=1;
        y=0;
    }
    else {
        exgcd(b,a%b,d,y,x);
        y-=(a/b)*x;
    }
}

练习题：

P1082 同余方程

P2613 【模板】有理数取余

P1516 青蛙的约会

2. 解一次同余方程组

2.1. 模数为素数的同余方程组

前置知识：exgcd，lcm，CRT

题目要求：给出 n，然后给出两个序列 a 和 p,求以下同余方程组

\begin{cases}x\equiv a_1\pmod{p_1}\\x\equiv a_2\pmod{p_2}\\……\\x\equiv a_n\pmod{p_n}\end{cases}

的最小自然数解。 数据保证 (p_i \in prime)。

对于这种模数为素数的同余方程组求解，我们使用 CRT（中国剩余定理） 求解。

void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(b==0){
        d=a;
        x=1;
        y=0;
    }
    else {
        exgcd(b,a%b,d,y,x);
        y-=(a/b)*x;
    }
}

ll China(int n,ll *m,ll *a){
    ll M=1,d,y,x=0;
    for(int i=0;i<n;i++)
        M*=m[i];
    for(int i=0;i<n;i++){
        ll w=M/m[i];
        exgcd(m[i],w,d,d,y);
        x=(x+y*w*a[i])%M;
    }
    return (x+M)%M;
}

2.2. 任意模数的同余方程组

前置知识：gcd，exgcd , 逆元，exCRT

题目要求：给出 n，然后给出两个序列 a 和 p,求以下同余方程组

\begin{cases}x\equiv a_1\pmod{p_1}\\x\equiv a_2\pmod{p_2}\\……\\x\equiv a_n\pmod{p_n}\end{cases}

的最小自然数解。

数据不保证 p_i 为素数。

因为 p_i 不保证为素数，所以我们无法使用普通的 CRT 求解，需要用到 exCRT。

int gcd(int x,int y){
    if(!y)return x;
    return gcd(y,x%y);
}

ll exgcd(ll a,ll b){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll res=exgcd(b,a%b);
    ll tmp=x;
    x=y;
    y=tmp-(a/b)*y;
    return res;
}

int inv(int a,int b) {
    exgcd(a,b);
    return ((x%b)+b)%b;
}

ll excrt(){
    for(int i=2;i<=n;i++){
        int M1=m[i-1],M2=m[i],C1=a[i-1],C2=a[i],T=gcd(M1,M2);
        if((C2-C1)%T!=0) {
            return -1;
        }
        m[i]=(M1*M2)/T;
        a[i]=(inv(M1/T,M2/T)*(C2-C1)/T)%(M2/T)*M1+C1;
        a[i]=((a[i]%m[i])+m[i])%m[i];
    }
    return a[n];
}

练习题：

P1495 【模板】中国剩余定理(CRT)/曹冲养猪

P3868 [TJOI2009]猜数字

P4777 【模板】扩展中国剩余定理（EXCRT）

P4774 [NOI2018] 屠龙勇士

3. 解高次同余方程指数

3.1. 模数为素数的高次同余方程求指数

前置知识：快速幂，hash表，BSGS

题目要求：给定一个质数 p，以及一个整数 b，一个整数 n，现在要求你计算一个最小的非负整数 l，满足 b^l\equiv n\pmod{p}。如果有 l 满足该要求，输出最小的 l，否则输出 no solution 。

对于这种求高次同余方程指数的题，使用 BSGS（大小步算法） 解决。

ll qpow(ll a,ll b,ll p){
    ll e=1;
    while(b){
        if(b&1)
            e=e*a%p;
        b>>=1;
        a=a*a%p;
    }
    return e%p;
}

void BSGS(){
    k.clear();
    if(b%p==0){
        printf("no solution");
        return 0;
    }
    bool vis=0;
    ll m=ceil(sqrt(p)),ans;
    for(ll i=0;i<=m;i++){
        if(i==0){
            ans=n%p;
            k[ans]=i;
            continue;
        }
        ans=(ans*b)%p;
        k[ans]=i;
    }
    ll t=qpow(b,m,p);
    ans=1;
    for(int i=1;i<=m;i++){
        ans=(ans*t)%p;
        if(k[ans]){
            ll o=i*m-k[ans];
            printf("%lld",(o%p+p)%p);
            vis=1;
            break;
        }
    }
    if(!vis)
        printf("no solution");
}

3.2. 任意模数的高次同余方程求指数

前置知识：exgcd，BSGS，exBSGS

题目要求：题目要求：a，b，p，现在要求你计算一个最小的非负整数 x，满足下式。

a^x\equiv b\pmod{p}

如果有 x 满足该要求，输出最小的 x，否则输出 no solution 。

不保证 p 为素数。

因为 p 不保证为素数，所以我们无法使用普通的 BSGS 求解，需要用到 exBSGS。

int exgcd(int a,int b,int &x,int &y){
    if(!b){x=1;y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

in ll ExBSGS(ll a,ll b,ll p){
    a%=p;b%=p;
    if(b==1||p==1)return 0;
    int d,ax=1,cnt=0,x,y;
    while((d=exgcd(a,p,x,y))^1){
        if(b%d)return -1;
        b/=d;p/=d;cnt++;
        ax=1ll*ax*(a/d)%p;
        if(ax==b)return cnt;
    }
    exgcd(ax,p,x,y);
    int inv=(x%p+p)%p;
    b=1ll*b*inv%p;
    k.clear();
    int t=ceil(sqrt(p)),val=1;
    for(int i=0;i<t;i++){
        k[1ll*b*val%p]=i;
        val=1ll*val*a%p;
    }
    a=val;val=1;
    if(!a)return !b?1+cnt:-1;
    for(int i=0,j;i<=t;i++){
        j=k.find(val)==k.end()?-1:k[val];
        if(~j&&i*t-j>=0)return i*t-j+cnt;
        val=1ll*val*a%p;
    }
    return -1;
}

练习题：

P3846 [TJOI2007] 可爱的质数/【模板】BSGS

P2485 [SDOI2011]计算器

P3306 [SDOI2013] 随机数生成器

P4884 多少个1？

P4454 [CQOI2018]破解D-H协议 我的题解

P4861 按钮

P4195 【模板】扩展 BSGS/exBSGS

4. 解二次同余方程底数

前置知识：（结构体）快速幂、Cipolla

题目要求：给出 n 和 p，求解方程。

x^2\equiv n\pmod{p}

数据保证 p 是奇素数。

对于这种同余方程，使用 cipolla 算法。

ll T,n,p;
ll w,a;
struct node{
    ll x,y;
    node operator * (const node& a)const{
        node z;
        z.x=(x*a.x%p+y*a.y%p*w%p)%p;
        z.y=(x*a.y%p+y*a.x%p)%p;
        return z;
    }
}u;

ll qpow(ll a,ll b,ll p){
    ll e=1;
    while(b){
        if(b&1)e=e*a%p;
        b>>=1;
        a=a*a%p;
    }
    return e%p;
}

node ndqpow(node x,ll y){
    node z;
    z.x=1;
    z.y=0;
    while(y){
        if(y&1)z=z*x;
        y>>=1;
        x=x*x;
    }
    return z;
}

int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld %lld",&n,&p);
        n%=p;
        if(p==2){
            puts("1");
            continue;
        }
        if(!n){
            puts("0");
            continue;
        }
        if(qpow(n,(p-1)>>1,p)==p-1){
            puts("Hola!");
            continue;
        }
        while(1){
            a=rand()%p;
            w=(a*a%p-n+p)%p;
            if(qpow(w,(p-1)>>1,p)==p-1)break;
        }
        u.x=a;
        u.y=1;
        u=ndqpow(u,(p+1)>>1);
        ll ans1=u.x,ans2=p-ans1;
        if(ans1>ans2)
            swap(ans1,ans2);
        if(ans1==ans2)
            printf("%lld\n",ans1);
        else 
            printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}

P5491 【模板】二次剩余

逃了