这道题就是扩展的中国剩余定理（模数不互质）
首先我们回忆一下中国剩余定理对于给定n个方程组x≡ai(mod pi)
令m=∏pi wi=m/pi，然后求解关于hi,ri的方程wi*hi+pi*ri=1
令ei=wi*hi,则x≡∑eiai (mod m) 简单的验证一下，拿每个pi去模x，
因为除了wi意外，其他wj都是pi的倍数，很容易发现是复合条件的
但是当pi不互质时，上述就失效了，所以我们不能再用中国剩余定理
我们就觉得办法是用增量法，假设现在已经得到满足前k个同余方程的最小解ans
对于下一个方程x≡a(mod p),
我们不难想到满足单一同余方程的解x=a+p*k，满足前k个同余方程的解x=ans+lcm(pi)*k
现在我们只要令a+p*k=ans+lcm(pi)*k'，找到这个二元一次方程的解
就能找到满足前k+1个同余方程的最小解，显然这是用扩展欧几里得解决
注意这道题说输入和输出可以用int64表示，但很容易中间量爆int64，理论用高精度
实际全部用long long好像就能过了（注意discuss中部分数据会造成中间量爆int64，但可以忽视……）
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<stdlib.h> 6 #define ll long long 7 using namespace std; 8 int k; 9 ll a1,a2,p1,p2,x,y; 10 11 ll gcd(ll a,ll b) 12 { 13 return (b==0)?a:gcd(b,a%b); 14 } 15 void exgcd(ll a,ll b,ll &x,ll &y) 16 { 17 if (b==0) {x=1; y=0; return;} 18 exgcd(b,a%b,x,y); 19 ll xx=x,yy=y; 20 x=yy; y=xx-(a/b)*yy; 21 } 22 23 int main() 24 { 25 while (scanf("%d",&k)!=EOF) 26 { 27 scanf("%lld%lld",&p1,&a1); 28 a1%=p1; 29 bool ch=0; 30 for (int i=2; i<=k; i++) 31 { 32 scanf("%lld%lld",&p2,&a2); 33 if (ch) continue; 34 a2%=p2; 35 ll g=gcd(p1,p2); 36 if ((a1-a2)%g) 37 { 38 ch=1; 39 continue; 40 } 41 ll a=p1/g,c=(a1-a2)/g; 42 exgcd(a,p2/g,x,y); y=(y+a)%a; 43 y=(y*c%a+a)%a; 44 p1=p1*(p2/g); a1=(a2+p2*y%p1)%p1; 45 } 46 if (ch) puts("-1"); 47 else printf("%lld ",a1); 48 } 49 system("pause"); 50 return 0; 51 }