80743 - 同测活动第4场提高组完善程序1
统计题目(材料题)
求解同余方程组: $x≡a_i (mod m_i), i=0,...,n-1$，输出$x$的最小正整数解，若无解则输出-1
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4 typedef long long ll;
5
6 ll exgcd(①) {
7 if (②) {
8 x = 1;
9 y = 0;
10 return a;
11 }
12 ll g = exgcd(b, a % b, y, x);
13 y = y - a / b * x;
14 return g;
15 }
16
17 ll mod(ll a, ll b) {
18 return (a % b + b) % b;
19 }
20
21 ll crt(vector<ll>& a, vector<ll>& m) {
22 int n = a.size();
23 ll a1 = a[0], m1 = m[0];
24
25 for (int i = 1; i < n; i++) {
26 ll a2 = a[i], m2 = m[i];
27 ll x, y;
28 ll g = exgcd(m1, m2, x, y);
29 if (3) return -1;
30
31 ll p, q;
32 exgcd(m1 / g, m2 / g, p, q);
33
34 ④;
35
36 ll x_val = (a1 + m1 * (a2 - a1) / g * p) % lcm;
37 a1 = mod(x_val, lcm);
38 m1 = lcm;
39 }
40 return ⑤;
41 }
42
43 int main() {
44 int n;
45 cin >> n;
46 vector<ll>a(n), m(n);
47 for (int i = 0; i < n; i++)//表示一个方程x≡a (mod m)
48 cin >> a[i] >> m[i];
49 ll res = crt(a, m);
50 if (res == -1) cout << -1 << endl;
51 else cout << res << endl;
52 return 0;
53 }
关注我们
