拓展中国剩余定理

对于一组同余方程对于一组同余方程对于一组同余方程

x ≡ a 1 ( m o d n 1 ) x≡a_1 (mod n_1) x≡a1(modn1)

x ≡ a 2 ( m o d n 2 ) x≡a_2 (mod n_2) x≡a2(modn2)

. . . ... ...

x ≡ a n ( m o d n n ) x≡a_n (mod n_n) x≡an(modnn)

模数 n 1 , n 2 . . . n n 两两不互质（不能用中国剩余定理），模数n_1,n_2...n_n两两不互质（不能用中国剩余定理），模数n1,n2...nn两两不互质（不能用中国剩余定理），

改用拓展中国剩余定理改用拓展中国剩余定理改用拓展中国剩余定理

通过先解出前两个方程的解，如将前两个方程通过先解出前两个方程的解，如将前两个方程通过先解出前两个方程的解，如将前两个方程

x ≡ a 1 ( m o d n 1 ) ， x ≡ a 2 ( m o d n 2 ) 化为 x ≡ A ( m o d N ) ， x≡a_1 (mod n_1)，x≡a_2 (mod n_2)化为x≡A(mod N)， x≡a1(modn1)，x≡a2(modn2)化为x≡A(modN)，

将此方程和 x ≡ a 3 ( m o d n 3 ) 将此方程和x≡a_3 (mod n_3) 将此方程和x≡a3(modn3)

继续联立求解，直到最后一个方程解完为止继续联立求解，直到最后一个方程解完为止继续联立求解，直到最后一个方程解完为止

1. 方法一 1. 方法一 1.方法一

x ≡ a 1 ( m o d n 1 ) x≡a_1 (mod n_1) x≡a1(modn1)

x ≡ a 2 ( m o d n 2 ) x≡a_2 (mod n_2) x≡a2(modn2)

可化为 x = a 1 + k 1 ∗ n 1 ① ; x = a 2 + k 2 ∗ n 2 ; 可化为 x=a_1+k_1*n_1 ①; x=a_2+k_2*n_2; 可化为x=a1+k1∗n1①;x=a2+k2∗n2;

消 x ，可得 a 1 + k 1 ∗ n 1 = a 2 + k 2 ∗ n 2 移项得到 k 1 ∗ n 1 + ( − k 2 ) ∗ n 2 = a 2 − a 1 消x，可得a_1+k_1*n_1=a_2+k_2*n_2 移项得到k_1*n_1+(-k_2)*n_2=a_2-a_1 消x，可得a1+k1∗n1=a2+k2∗n2移项得到k1∗n1+(−k2)∗n2=a2−a1

令 g = g c d ( n 1 , n 2 ) , d = a 2 − a 1 , x = k 1 , y = − k 2 ; 令g=gcd(n_1,n_2), d=a_2-a_1, x=k_1, y=-k_2; 令g=gcd(n1,n2),d=a2−a1,x=k1,y=−k2;

上式化为 x ∗ n 1 + y ∗ n 2 = d ③ 上式化为 x*n_1+y*n_2=d ③ 上式化为x∗n1+y∗n2=d③

用拓展欧几里得解线性方程（此处求解 x 1 ， y 1 ） x 1 ∗ n 1 + y 1 ∗ n 2 = g 用拓展欧几里得解线性方程（此处求解x_1，y_1）x_1*n_1+y_1*n_2=g 用拓展欧几里得解线性方程（此处求解x1，y1）x1∗n1+y1∗n2=g

式子可化为 x 1 ∗ ( d / g ) ∗ n 1 + y 1 ∗ ( d / g ) ∗ n 2 = g ∗ ( d / g ) 和 ③ 相同的式子式子可化为 x_1*(d/g)*n_1+y_1*(d/g)*n_2 = g*(d/g) 和③相同的式子式子可化为x1∗(d/g)∗n1+y1∗(d/g)∗n2=g∗(d/g)和③相同的式子

即 x = x 1 ∗ ( d / g ) = k 1 ; y = y 1 ∗ ( d / g ) = − k 2 ; 即x=x_1*(d/g)=k_1 ; y=y_1*(d/g)=-k_2; 即x=x1∗(d/g)=k1;y=y1∗(d/g)=−k2;

即 k 1 = x 1 ∗ ( d / g ) ; k 2 = − y 1 ∗ ( d / g ) 即k_1=x_1*(d/g); k_2=-y_1*(d/g) 即k1=x1∗(d/g);k2=−y1∗(d/g)

一组通解为 k 1 = k 1 + ( n 2 / g ) ∗ T ; k 2 = k 2 − ( n 1 / g ) ∗ T 一组通解为 k_1=k_1+(n_2/g)*T; k_2=k_2-(n_1/g)*T 一组通解为k1=k1+(n2/g)∗T;k2=k2−(n1/g)∗T

要求使所求得的解最小且为正整数则可以根据 k 1 的通解形式求得 ( 消掉 T 的影响 ) 要求使所求得的解最小且为正整数则可以根据 k_1的通解形式求得(消掉T的影响) 要求使所求得的解最小且为正整数则可以根据k1的通解形式求得(消掉T的影响)

k 1 = ( k 1 m o d ( n 2 / g ) + ( n 2 / g ) ) m o d ( n 2 / g ) ② ，即 k 1 = ( ( x 1 ∗ ( d / g ) ) m o d ( n 2 / g ) + ( n 2 / g ) ) m o d ( n 2 / g ) k_1=(k_1 mod (n_2/g)+(n_2/g)) mod (n_2/g) ②，即k_1=((x_1*(d/g)) mod (n_2/g)+(n_2/g)) mod (n_2/g) k1=(k1mod(n2/g)+(n2/g))mod(n2/g)②，即k1=((x1∗(d/g))mod(n2/g)+(n2/g))mod(n2/g)

将求出的 k 1 带入 ① ，可得 x 的解，作为下一次的 A ， N 将求出的k_1带入①，可得x的解，作为下一次的A，N 将求出的k1带入①，可得x的解，作为下一次的A，N为 l c m ( n 1 , n 2 ) lcm(n1,n2) lcm(n1,n2)

即 A 为合并后的 a ， N 为合并后的 n 即A为合并后的a，N为合并后的n 即A为合并后的a，N为合并后的n

ll excrt(){
    ll a1=b[0],n1=a[0],a2,n2,d,x,y,gcd;//余数 b[] 除数 a[]
    // 返回的是最小非负整数解，有些题目需要特判
    //若当余数为0的时候 题目要求求正整数 所以0不算在内，应该加上下面的注释，即余数等于除数，同理后面的板子
    //if(a1==0)a1=a[0]
    for(int i=1;i<n;i++){
        a2=b[i];n2=a[i];
        d=a2-a1;
        gcd=exgcd(n1,n2,x,y);
        if(d%gcd)return -1;
        x=((x*d/gcd)%(n2/gcd)+(n2/gcd))%(n2/gcd);
        a1=x*n1+a1;
        n1=n1*n2/gcd;
    }
    return a1;
}

此处补充一下拓展欧几里得求解 a ∗ x + b ∗ y = g c d ( a , b ) 此处补充一下拓展欧几里得求解a*x+b*y=gcd(a,b) 此处补充一下拓展欧几里得求解a∗x+b∗y=gcd(a,b)

简单推导：简单推导：简单推导：

a ∗ x 1 + b ∗ y 1 = g c d ( a , b ) ① a*x_1+b*y_1=gcd(a,b) ① a∗x1+b∗y1=gcd(a,b)①

b ∗ x 2 + ( a m o d b ) ∗ y 2 = g c d ( a , b ) ② b*x_2+(a mod b)*y_2=gcd(a,b) ② b∗x2+(amodb)∗y2=gcd(a,b)②

联立 ① 和 ② ，按照解方程思路可得 a ∗ x 1 + b ∗ y 1 = b ∗ x 2 + ( a − a / b ∗ b ) ∗ y 2 联立①和②，按照解方程思路可得 a*x_1+b*y_1=b*x_2+(a-a/b*b)*y_2 联立①和②，按照解方程思路可得a∗x1+b∗y1=b∗x2+(a−a/b∗b)∗y2

通过移项得 a ∗ x 1 + b ∗ y 1 = a ∗ y 2 + b ∗ ( x 2 − a / b ∗ y 2 ) 通过移项得 a*x_1+b*y_1=a*y_2+b*(x_2-a/b*y_2) 通过移项得a∗x1+b∗y1=a∗y2+b∗(x2−a/b∗y2)

x 1 = y 2 x_1=y_2 x1=y2

y 1 = x 2 − a / b ∗ y 2 y_1=x_2-a/b*y_2 y1=x2−a/b∗y2

//a*x+b*y=gcd(a,b)
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(a==0&&b==0)return -1;
    if(b==0){x=1;y=0;return a;}
    ll d=exgcd(b,a%b,y,x);//x和y交换了
    y-=a/b*x;
    return d;
}

2. 方法二 2. 方法二 2.方法二

设方程为 x ≡ a i ( m o d b i ) 设方程为 x≡a_i(mod b_i) 设方程为x≡ai(modbi)

前 k − 1 个方程组构成的一个解，记作 x ，记 m = l c m ( l c m ( b 1 , b 2 ) , b 3 ) 依次类推到 k − 1 前k−1个方程组构成的一个解，记作x，记m=lcm(lcm(b1,b2),b3)依次类推到k-1 前k−1个方程组构成的一个解，记作x，记m=lcm(lcm(b1,b2),b3)依次类推到k−1

则 x + i ∗ m （ i 属于正整数） ① 是前 k − 1 个方程的通解则x+i*m（i属于正整数）① 是前k-1个方程的通解则x+i∗m（i属于正整数）①是前k−1个方程的通解

对于第 k 个式子，假设有 t 能够满足 ① ，即 x + t ∗ m = a k ( m o d b k ) ② （而后的每一个 x ′ = x + t ∗ m ，循环 n 次得到最终答案）对于第k个式子，假设有t能够满足①，即x+t*m=ak(mod bk) ②（而后的每一个x'=x+t*m，循环n次得到最终答案）对于第k个式子，假设有t能够满足①，即x+t∗m=ak(modbk)②（而后的每一个x′=x+t∗m，循环n次得到最终答案）

用拓展欧几里得求 a x ≡ b ( m o d m ) ② 式可化为求 t 的同余方程，则 m ∗ t ≡ ( a k − x ) ( m o d b k ) ③ 用拓展欧几里得求 ax≡b(mod m) ②式可化为求t的同余方程，则 m*t≡(a_k-x) (mod b_k) ③ 用拓展欧几里得求ax≡b(modm)②式可化为求t的同余方程，则m∗t≡(ak−x)(modbk)③

设 x ， y ③ 式转化为 m ∗ x + b k ∗ y = a k − x 设x，y ③式转化为 m*x+b_k*y=a_k-x 设x，y③式转化为m∗x+bk∗y=ak−x

由扩展欧几里得我们可知存在 x 1 和 y 1 ，有 m ∗ x 1 + b k ∗ y 1 = g c d ( m , b k ) ④ 由扩展欧几里得我们可知存在x_1和y_1，有m*x_1+b_k*y_1=gcd(m,b_k) ④ 由扩展欧几里得我们可知存在x1和y1，有m∗x1+bk∗y1=gcd(m,bk)④

④ 可化为 m ∗ x 1 ∗ ( a k − x ) / g c d ( m , b k ) + b k ∗ y 1 ∗ ( a k − x ) / g c d ( m , b k ) = a k − x ④可化为 m*x_1*(a_k-x)/gcd(m,b_k)+b_k*y_1*(a_k-x)/gcd(m,b_k)=a_k-x ④可化为m∗x1∗(ak−x)/gcd(m,bk)+bk∗y1∗(ak−x)/gcd(m,bk)=ak−x

所以 x = x 1 ∗ ( a k − x ) / g c d ( m , b k ) , y = y 1 ∗ ( a k − x ) / g c d ( m , b k ) 所以x=x_1*(a_k-x)/gcd(m,b_k), y=y_1*(a_k-x)/gcd(m,b_k) 所以x=x1∗(ak−x)/gcd(m,bk),y=y1∗(ak−x)/gcd(m,bk)

则 t = x = x 1 ∗ ( a k − x ) / g c d ( m , b k ) 则t=x=x_1*(a_k-x)/gcd(m,b_k) 则t=x=x1∗(ak−x)/gcd(m,bk)

带回去 ① 可得 x ′ = x + ( x 1 ∗ ( a k − x ) / g c d ( m , b k ) ) ∗ m 其中还有求余，要 m o d b k ，还要让结果（即代码 a 0 = ( a 0 + b 0 ) m o d b 0 见下面）变成正数（或者直接 m o d ( b k / g c d ( m , b k ) ) ）带回去①可得 x'=x+(x_1*(a_k-x)/gcd(m,b_k))*m 其中还有求余，要mod b_k，还要让结果（即代码 a_0=(a_0+b_0)modb_0 见下面）变成正数（或者直接mod (bk/gcd(m,bk))）带回去①可得x′=x+(x1∗(ak−x)/gcd(m,bk))∗m其中还有求余，要modbk，还要让结果（即代码a0=(a0+b0)modb0见下面）变成正数（或者直接mod(bk/gcd(m,bk))）

m 还要进行变化，即 m = m ∗ b k / g c d ( m , b k ) m还要进行变化，即 m=m*b_k/gcd(m,b_k) m还要进行变化，即m=m∗bk/gcd(m,bk)

//china x=ai(mod bi) a除数 b余数 
ll excrt(){
    ll x,y,a0=a[0],b0=b[0],a1,b1,gcd;
    for(int i=1;i<n;i++){
        a1=((a[i]-a0)%b[i]+b[i])%b[i],b1=b[i];
        gcd=exgcd(b0,b1,x,y);
        if(a1%gcd)return -1;
        x=x*(a1/gcd)%b1;
        a0+=x*b0;
        b0*=b1/gcd;
        a0=(a0+b0)%b0;//change the sgn of a0
    } 
    return a0;
}

或者或者或者

//china a除数 b余数
ll excrt(){
    ll x,y,aa,bb,gcd;
    ll m=a[0],ans=b[0];//a[] divide b[] mod
    for(int i=1;i<n;i++){
        aa=a[i],bb=b[i];
        bb=((bb-ans)%aa+aa)%aa;
        gcd=exgcd(m,aa,x,y);
        if(bb%gcd)return -1;
        x=x*(bb/gcd)%(aa/gcd);
        x=(x+aa)%(aa/gcd);//change the sgn of x, because x maybe - change to +
        ans+=x*m;
        m=m/gcd*aa;
    }
    return ans;
}

附上 i n t 128 的读入写入附上int128的读入写入附上int128的读入写入

typedef __int128 ll;
int scan(ll &x){
    x=0;int sgn=1;
    char ch;
    while(ch=getchar()){
        if(ch==EOF)return EOF;
        else if(ch=='-')sgn=-sgn;
        else if(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');break;
        }
    }
    while((ch=getchar())>='0'&&ch<='9')x=x*10+(ch-'0');
    x*=sgn;return 1;
}
void _print(ll x){
    if(x>9)_print(x/10);
    putchar(x%10+'0');
}
void print(ll x){
    if(x<0){x=-x;putchar('-');}
    _print(x);
}