HDU 3579 中國剩餘定理模數不互質

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn = 1000+10;
 5 
 6 class Extend_Euclid{
 7 
 8 private:
 9     int size_e = 0; // number of equations
10     int max_size; //
11     int a[maxn];
12     int m[maxn];
13 
14     /*
15     * no need to make sure that a is nl then b
16     */
17     ll gcd(ll a, ll b){
18         return b ? gcd(b, a%b) : a;
19     }
20 
21     /*
22     * if you want the minimal non-neg x, (x mod b+b) mod b is the answer
23     */
24     void extend_Euclid(ll a, ll b, ll &x, ll &y){
25         if(b==0){
26             x = 1;
27             y = 0;
28             return;
29         }
30         extend_Euclid(b, a%b, x, y);
31         ll tmp = x;
32         x = y;
33         y = tmp-(a/b)*y;
34     }
35 
36     bool merge(ll a1, ll m1, ll a2, ll m2, ll &new_a, ll &new_m){
37 
38         if((a1-a2) % gcd(m1, m2) != 0){
39             //cout <<"here: " <<a1-a2 <<' ' << gcd(m1, m2) <<'\n';
40             return false;
41         }
42 
43         ll x=0, y=0;
44         extend_Euclid(m1, m2, x, y);
45         new_a = a1 - m1/gcd(m1, m2)*x*(a1-a2);
46         new_m = m1*m2/gcd(m1, m2);
47         //new_a = a2 + m2/gcd(m1, m2)*y*(a1-a2);
48         new_a = (new_a%new_m + new_m) % new_m;
49         return true;
50     }
51 
52 public:
53     Extend_Euclid(int size){
54         size_e = size;
55     }
56 
57     void read(){
58         for (int i = 0; i < size_e; ++i){
59             cin >>m[i];
60         }
61         for (int i = 0; i < size_e; ++i){
62             cin >>a[i];
63         }
64     }
65 
66     ll solve(){
67         //cout <<gcd(14, 57) <<'\n';
68         //merge equation i and i-1
69         ll new_a=a[0], new_m=m[0];
70         for (int i = 1; i < size_e; ++i){
71             if(!merge(new_a, new_m, a[i], m[i], new_a, new_m)){
72                 return -1;
73             }
74         }
75         ll res = (new_a%new_m + new_m) % new_m;
76         if(res==0) return new_m;
77         else return res;
78     }
79 
80 };
81 
82 int main(){
83     int T, n, cnt=0;
84     cin >>T;
85     while(T--){
86         cin >>n;
87         Extend_Euclid ee(n);
88         ee.read();
89         ll res = ee.solve();
90         cout <<"Case " <<++cnt <<": ";
91 
92         cout <<res <<'\n';
93 
94     }
95     return 0;
96 }