其实打了CRT和exCRT很多遍了打完就忘……后来发现是因为我老是看到一些写的极其复杂的博客……

模板题

现在有n个形如$ x \equiv a_i \pmod {b_i}$的方程
假设前k-1个方程的最小正整数解是$ans_{k-1},$
令$M=lcm(b_1,b_2,……,b_{k-1})$
设$ans_k=ans_{k-1}+xM(x为整数)$
则$ans_{k-1}+xM \equiv a_k \pmod {b_k}$
$∴Mx\equiv {{a_k}-{ans_{k-1}}} \pmod {b_k}$
$Mx+{b_k}y={{a_k}-{ans_{k-1}}} $
exgcd。
题目的a,b读入是反的，注意。 还有记得开longlong。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
LL ans,M=1; 
LL gcd(LL x,LL y){ return y?gcd(y,x%y):x; } 
LL lcm(LL x,LL y){ return x*y/gcd(x,y); }
LL exgcd(LL A,LL B,LL &x,LL &y){
    if(!B){ x=1,y=0;return x; }
    else{
        LL d=exgcd(B,A%B,y,x);
        y-=A/B*x;return d;
    }
} 
void crt(LL A,LL B){
    LL a=M,b=B,c=((A-ans)%B+B)%B,x,y;
    LL g=exgcd(a,b,x,y);
    if(c%g) return;
    x=((x*(c/g))%B+B)%B;ans+=x*M;
    M=lcm(M,B);ans=(ans%M+M)%M;
} 
int main(){
    scanf("%d",&n);
    LL a,b;
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a,&b),crt(b,a);
    printf("%lld\n",ans);
    return 0;
}