照着教程想了一下午，终于A了。。。
参考文章：
https://www.luogu.org/blog/niiick/solution-p4777
https://www.luogu.org/problemnew/solution/P4777
https://blog.csdn.net/xiaobian_/article/details/87949337
https://www.cnblogs.com/yangsongyi/p/9867057.html
（快速乘规避溢出）
https://www.cnblogs.com/jt2001/p/6129914.html
https://blog.csdn.net/qq_39599067/article/details/81118467
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include<iostream> #include<vector> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; int n; ll b[100005], a[100005]; //b是余数，a是模数 ll quickmultiply(ll a, ll b,ll mod) { if (b == 0)return 0; ll result = quickmultiply(a, b / 2, mod) % mod; result = 2*result%mod; if (b & 1)result = (result+a)%mod; return result; } ll ngcd(ll a, ll b) { return b == 0 ? a : ngcd(b, a % b); } ll exgcd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1; y = 0; return a; } ll d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } ll excrt() { ll lcm = a[1], ans = b[1]; for (int i = 2; i <= n; i++) { ll k1, k2, K, mod = lcm; ll gcd = exgcd(lcm, a[i], k1, k2); ll minus = ((b[i] - ans) % a[i] + a[i]) % a[i]; if ((minus % ngcd(lcm, a[i]) != 0))return -1; K = (quickmultiply(k1,(minus / gcd),(a[i] / gcd)) + a[i] / gcd) % (a[i] / gcd); lcm *= a[i] / gcd, ans = (K * mod + ans) % lcm; } return (ans % lcm + lcm) % lcm; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; } cout<<excrt(); } |