# 洛谷 P4777 【模板】扩展中国剩余定理（EXCRT）

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

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546 #include #include #include #include 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<