poj 2891 Strange Way to Express Integers

http://poj.org/problem?id=2891

这道题的题意是：给你多个模性方程组：m mod ai=ri 求最小的m；

中国剩余定理

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define ll long long
 5 using namespace std;
 6 
 7 ll gcd(ll a,ll b,ll &x,ll &y)
 8 {
 9     if(!b)
10     {
11         x=1;
12         y=0;
13         return a;
14     }
15     ll d=gcd(b,a%b,y,x);
16     y-=x*(a/b);
17     return d;
18 }
19 
20 int main()
21 {
22     ll a1,t,r1,x,y,a2,r2;
23     while(scanf("%lld",&t)!=EOF)
24     {
25         scanf("%lld%lld",&a1,&r1);
26         t--;
27         bool flag=true;
28         while(t--)
29         {
30             scanf("%lld%lld",&a2,&r2);
31             if(!flag) continue;
32             ll d1=gcd(a1,a2,x,y);
33             ll c=r2-r1;
34             if(c%d1)
35             {
36                 flag=false;
37                 continue;
38             }
39             ll t1=a2/d1;
40             x=(c/d1*x%t1+t1)%t1;
41             r1=(a1*x+r1);
42             a1=a1*a2/d1;    
43         }
44         if(!flag) printf("-1
");
45         else printf("%lld
",r1);
46     }
47     return 0;
48 }

View Code