中国剩余定理及其拓展学习笔记

中国剩余定理：

大概就是有这么一个问题：

⎧⎩⎨⎪⎪⎪⎪⎪⎪x≡c1(mod p1)x≡c2(mod p2)…x≡cn(mod pn) { x ≡ c 1 ( m o d   p 1 ) x ≡ c 2 ( m o d   p 2 ) … x ≡ c n ( m o d   p n )

保证 pi p i 之间都互质，然后让你求 x x 。古人给了我们一种巧妙的方法，那就是构造答案，如果我们能够求出分别满足每一个方程的xx，即 x≡ci(mod pi) x ≡ c i ( m o d   p i ) （用拓展欧几里得来求解），并且保证这个 x x 是其他所有的模数的倍数的话，那么我们只要把这nn个 x x 相加就好了，这时我们会发现，正是因为pipi之间互质，才可以使得这个巧妙的构造方法得以实现。

拓展中国剩余定理：

但是题目有时候并不是保证 pi p i 互质的，所以我们要用拓展中国剩余定理。虽然说和中国剩余完全不同，但是还是叫了这个名字。这里采用合并同余方程的方法来求解。原式可以做如下变形：

{x=c1+k1∗p1x=c2+k2∗p2 { x = c 1 + k 1 ∗ p 1 x = c 2 + k 2 ∗ p 2

其中 k1,k2 k 1 , k 2 可以看做是两个变量，然后为了让 x x 满足条件，我们来寻找k1,k2k1,k2之间的关系：

c1+k1∗p1=c2+k2∗p2  k1∗p1=k2∗p2+c2−c1 c 1 + k 1 ∗ p 1 = c 2 + k 2 ∗ p 2     k 1 ∗ p 1 = k 2 ∗ p 2 + c 2 − c 1

由于我们要求的是整数解，显然有解的条件是 gcd(p1,p2)|(c2−c1) gcd ( p 1 , p 2 ) | ( c 2 − c 1 ) ，设 d=gcd(p1,p2) d = gcd ( p 1 , p 2 ) ，将两边同时除以 d d 之后即可以转化为同余方程直接乘以一个逆元之后将k1k1放在等式的左边。

k1∗p1d=k2∗p2d+c2−c1dk1∗p1d≡c2−c1d(mod  p2d)k1≡c2−c1d∗inv(p1d)(mod  p2d)k1=c2−c1d∗inv(p1d)+y∗p2d k 1 ∗ p 1 d = k 2 ∗ p 2 d + c 2 − c 1 d k 1 ∗ p 1 d ≡ c 2 − c 1 d ( m o d     p 2 d ) k 1 ≡ c 2 − c 1 d ∗ i n v ( p 1 d ) ( m o d     p 2 d ) k 1 = c 2 − c 1 d ∗ i n v ( p 1 d ) + y ∗ p 2 d

这个时候我们得到的 k1和k2 k 1 和 k 2 的关系同时也得到的 k1 k 1 的表达式，将它带入原方程中得： x=p1∗c2−c1d∗inv(p1d,p2d)+c1+y∗p1∗p2dx≡p1∗c2−c1d∗inv(p1d,p2d)(mod  p1∗p2d) x = p 1 ∗ c 2 − c 1 d ∗ i n v ( p 1 d , p 2 d ) + c 1 + y ∗ p 1 ∗ p 2 d x ≡ p 1 ∗ c 2 − c 1 d ∗ i n v ( p 1 d , p 2 d ) ( m o d     p 1 ∗ p 2 d )

然后就合并完了，接下来就只要一直合并下去就好了。

/*===========================
 * Auhthor : ylsoi
 * Problem : luogu4777
 * Algodithm : ExCRT
 * Time : .
 * =========================*/
#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;

using namespace std;

void File(){
    freopen("luogu4777.in","r",stdin);
    freopen("luogu4777.out","w",stdout);
}

const int maxm=e5+;
int T,n,m;
ll p[maxm],c[maxm];

ll qmul(ll x,ll b,ll mod){
    ll ret=,base=x%mod,mul=;
    if(b<)b*=-,mul=-;
    while(b){
        if(b&)ret=(ret+base)%mod;
        base=(base+base)%mod;
        b>>=;
    }
    return ret*mul;
}

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

ll get_inv(ll a,ll b){
    ll x,y;
    x/=exgcd(a,-b,x,y);
    return (x%b+b)%b;
}

void work(){
    REP(i,,m){
        ll d=__gcd(p[],p[i]),tmp=p[];
        p[]=p[]/d*p[i];
        c[]=qmul(qmul(tmp,(c[i]-c[])/d,p[]),get_inv(tmp/d,p[i]/d),p[])+c[];
        c[]%=p[];
    }
    c[]=(c[]+p[])%p[];
    printf("%lld\n",c[]);
}

int main(){
    File();
    scanf("%d",&m);
    REP(i,,m)scanf("%lld%lld",&p[i],&c[i]);
    work();
    return ;
}