HDU 3579 Hello Kiki(中国の残りの定理は互いに質を持たないバージョン)
8717 ワード
タイトルリンク
理解しないで、分からないで、互いに質を交換しない時、構想は2つの方程式が1つに合併して、更に合併して、最後に結果を求めます...このブログはいいですね.
理解しないで、分からないで、互いに質を交換しない時、構想は2つの方程式が1つに合併して、更に合併して、最後に結果を求めます...このブログはいいですね.
1 #include <cstdio>
2 #include <cstring>
3 #include <map>
4 #include <cmath>
5 using namespace std;
6 #define ll __int64
7 ll p[11],o[11];
8 ll x,y;
9 ll ext_eulid(ll a,ll b)
10 {
11 ll t,d;
12 if(b == 0)
13 {
14 x = 1;
15 y = 0;
16 return a;
17 }
18 d = ext_eulid(b,a%b);
19 t = x;
20 x = y;
21 y = t - (a/b)*y;
22 return d;
23 }
24 ll gcd(ll a,ll b)
25 {
26 return b == 0?a:gcd(b,a%b);
27 }
28 int main()
29 {
30 int t,i,n,z,num = 0;
31 ll p1,o1,d,c,mod;
32 scanf("%d",&t);
33 while(t--)
34 {
35 scanf("%d",&n);
36 for(i = 1;i <= n;i ++)
37 scanf("%I64d",&p[i]);
38 for(i = 1;i <= n;i ++)
39 scanf("%I64d",&o[i]);
40 p1 = p[1];o1 = o[1];
41 z = 1;
42 for(i = 2;i <= n&&z;i ++)
43 {
44 d = ext_eulid(p1,p[i]);
45 c = o[i] - o1;
46 if(c%d) z = 0;//
47 mod = p[i]/d;
48 x = ((c/d*x)%mod+mod)%mod;
49 o1 = p1*x + o1;
50 p1 = p1*mod;
51 }
52 if(!z)
53 {
54 printf("Case %d: -1
",++num);
55 continue;
56 }
57 if(o1 == 0)//
58 {
59 o1 = 1;
60 for(i = 1;i <= n;i ++)
61 o1 = o1*p[i]/gcd(o1,p[i]);
62 }
63 printf("Case %d: %I64d
",++num,o1);
64 }
65 return 0;
66 }