hiho1303（模线性方程组）

题目连接：https://hihocoder.com/problemset/problem/1303?sid=1077620#

还不是很理解。。。。

 1 #include<cstdio>
 2 #define ll long long
 3 
 4 ll a,b,c;
 5 ll x,y;
 6 
 7 ll r[1010],m[1010];
 8 void exgcd(ll a,ll b,ll& d,ll &x, ll &y)
 9 {
10    if(!b)
11    {
12        d=a;
13        x=1;
14        y=0;
15    }
16    else
17    {
18        exgcd(b,a%b,d,y,x);
19        y-=x*(a/b);
20    }
21 }
22 
23 ll crt(int n)
24 {
25     ll M=m[1],R=r[1],x,y,d;
26     for(int i=2;i<=n;i++)
27     {
28         exgcd(M,m[i],d,x,y);
29         if( (r[i]-R)%d ) return -1;
30         x=(r[i]-R)/d*x%(m[i]/d);  //不懂为什么取模
31         R+=M*x;
32         M=M/d*m[i];  //这块一开始写成 M=M*m[i]/d;  调了好久-_-|| 
33         R%=M;
34     }
35     if(R<0) R+=M;
36     return R;
37 }
38 
39 int main()
40 {
41     int n;
42     scanf("%d",&n);
43     {
44         for(int i=1;i<=n;i++)
45         {
46             scanf("%lld%lld",&m[i],&r[i]);
47         }
48         ll ans=crt(n);
49         printf("%lld
",ans);
50     }
51 
52 
53 
54 }