poj 2891 Strange Way to Express Integers
6427 ワード
http://poj.org/problem?id=2891
この問題の題意は:あなたに複数のモジュール方程式のグループをあげます:m mod ai=riは最小のmを求めます;
中国の残りの定理
View Code
この問題の題意は:あなたに複数のモジュール方程式のグループをあげます: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