引入

形如

x \equiv r_1 ( \mod p_1)

x \equiv r_2 ( \mod p_2)

……

x \equiv r_n ( \mod p_n)

的方程组称为同余方程组.

当p两两互质时,该方程一定有解,且有无穷多解.求解的方法称为中国剩余定理,又名孙子定理.别名中国单身狗定理

定理内容

互质形式

首先令

P=\prod_{i=1}^np_i

定义

P_i=\frac{P}{p_i}

设

t_i=Inv(P_i,p_i)

则方程的一个特解为

x_0=(\sum_{i=1}^nr_iP_it_i \mod P)

通解形式为

x=x_0+kP

一般形式

在这种形式下,模数不一定两两互质,此时方程可能存在无解的情况.求解这种形式的方程组有两种方法,一种是将不互质的模数转化为互质的模数,另一种是同余方程组合并.第一种方法实际操作较为复杂,而且存在溢出的问题,故下面只介绍第二种方法.

考虑以下两个线性方程组:

x \equiv r_1 ( \mod p_1)

x \equiv r_2 ( \mod p_2)

将方程转化为等式形式,有

p_1k_1+r_1=p_2k_2+r_2

移项

p_1k_1-p_2k_2=r_2-r_1

换元

ax+by=c

利用拓展欧几里得求出该方程组通解后,代入原同余方程组中即可得到一个特解

x_0

显然,通解形式为

x_0+LCM(p_1,p_2)

至此,方程组转化成了一个同余方程

x \equiv (r_2-r_1 \mod LCM(p_1,p_2))

不断重复以上过程即可求解.

这种方法弥补了中国剩余定理不能解决模数不两两互质的缺陷,而且一般不会存在乘法溢出问题.

模板

中国剩余定理

for (i=1;i<=m;i++){
    cnt=(r[i]*(M/p[i]))%M;
    cnt=(cnt*Ni(M/p[i],p[i]-2,p[i]))%M;
    Ans=(Ans+cnt)%M;
}

一般形式

inline LL Gcd(LL a,LL b){return (!b)?a:Gcd(b,a%b);}

inline void Ex_gcd(LL a,LL b,LL &x,LL &y){
    LL p=0,q=0;
    if (b==0) {
        x=1;    y=0;    return;
    }   else {
        Ex_gcd(b,a%b,p,q);
        x=q;    y=p-a/b*q;
    }
}

inline LL Solve(){
    int i=0;
    LL a=0,b=0,c=0,gcd=0,k1=0,k2=0;
    for (i=1;i<n;i++){
        a=p[i]; b=p[i+1];   c=r[i+1]-r[i];
        gcd=Gcd(a,b);
        if (c%gcd)  return -1;
        a/=gcd; b/=gcd; c/=gcd;
        Ex_gcd(a,b,k1,k2);
        k1=((k1*c)%b+b)%b;
        p[i+1]=p[i]/gcd*p[i+1];
        r[i+1]=(k1*p[i]%p[i+1]+r[i])%p[i+1];
    }
    return r[n];
}

例题

[COGS1786]韩信点兵

链接

COGS1786

题意

求解模数互质的同余方程组.

完整代码

#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define N 55
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int i;
LL n,M,m,cnt,Ans;
LL r[N],p[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline LL Ni(LL x,LL y,LL MOD){
    LL p=x,t=1,Res=1;
    for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
    return Res;
}

int main(){
    freopen("HanXin.in","r",stdin);
    freopen("HanXin.out","w",stdout);
    scanf("%lld%d",&n,&m);
    for (i=1;i<=m;i++)  scanf("%lld%lld",&p[i],&r[i]);
    M=1;
    for (i=1;i<=m;i++)  M*=p[i];
    Ans=0;
    for (i=1;i<=m;i++){
        cnt=(r[i]*(M/p[i]))%M;
        cnt=(cnt*Ni(M/p[i],p[i]-2,p[i]))%M;
        Ans=(Ans+cnt)%M;
    }
    if (Ans>n)  cout<<"-1"<<endl;
    else {
        while (Ans+M<n) Ans+=M;
        cout<<n-Ans<<endl;
    }
    return 0;
}

[COGS2160]丧心病狂的韩信大点兵

链接

COGS2160

题意

求解一般形式的同余方程组.

完整代码

#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define N 1010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i;
LL p[N],r[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline LL Gcd(LL a,LL b){return (!b)?a:Gcd(b,a%b);}

inline void Ex_gcd(LL a,LL b,LL &x,LL &y){
    LL p=0,q=0;
    if (b==0) {
        x=1;    y=0;    return;
    }   else {
        Ex_gcd(b,a%b,p,q);
        x=q;    y=p-a/b*q;
    }
}

inline LL Solve(){
    int i=0;
    LL a=0,b=0,c=0,gcd=0,k1=0,k2=0;
    for (i=1;i<n;i++){
        a=p[i]; b=p[i+1];   c=r[i+1]-r[i];
        gcd=Gcd(a,b);
        if (c%gcd)  return -1;
        a/=gcd; b/=gcd; c/=gcd;
        Ex_gcd(a,b,k1,k2);
        k1=((k1*c)%b+b)%b;
        p[i+1]=p[i]/gcd*p[i+1];
        r[i+1]=(k1*p[i]%p[i+1]+r[i])%p[i+1];
    }
    return r[n];
}

int main(){
    freopen("weakhanxin.in","r",stdin);
    freopen("weakhanxin.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++)  scanf("%lld%lld",&p[i],&r[i]);
    printf("%lld\n",Solve());
    return 0;
}