中國剩餘定理及其拓展學習筆記

中國剩餘定理：

大概就是有這麼一個問題：

⎧⎩⎨⎪⎪⎪⎪⎪⎪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 ;
}