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

    	考虑签名两条方程， x=r[1](mod m[1])， x=r[1](mod m[2])
    	转化为不定方程  x = m[1] * p + r[1] = m[2] * q + r2
    	那么 m[1] * p - m[2] * q = r[2] - r[1]
    	gcd(m[1], m[2]) 整除 r[2] - r[1] 说明有解，否则无解
    	由扩展欧几里得算法求出方程 m[1] * p - m[2] * q = r[2] - r[1] 一组特解，
    	再得到通解，最后这两条方程等价合并为一个新的方程式
    	x = r(mod m),  再用这新的方程 去和第 3条方程联解，以此类推， 
    	n个同余方程，合并 n - 1 
    
    
      
      
      
      
      
      
      
      
    

    #include <bits/stdc++.h>
    using namespace std;
    typedef __int128 ll;
    const int MaxN = 1e5 + 10;
    int n;
    ll r[MaxN], m[MaxN];
    
    ll exgcd(ll a, ll b, ll& x, ll& y)
    {
    	if(0 == b)
    	{
    		x = 1, y = 0; return a;
    	}
    	ll d, x1, y1;
    	d = exgcd(b, a % b, x1, y1);
    	x = y1, y = x1 - a / b * y1;
    	return d;
    }
    
    ll exCRT(ll m[], ll r[], int n)
    {
    	ll m1, m2, r1, r2, p, q;
    	m1 = m[1], r1 = r[1];
    	for(int i = 2; i <= n; ++i)
    	{
    		m2 = m[i], r2 = r[i];
    		ll d = exgcd(m1, m2, p, q);
    		if((r2 - r1) % d)
    		{
    			return -1;
    		}
    		ll tmp = (r2 - r1) /d;
    		p = p * tmp;	//特解
    		p = (p %(m2 / d) + m2 / d) % (m2 / d);	//使得 p 模 (m2 / d) 为非负数
    		r1 = m1 * p + r1;
    		m1 = (m2 / d) * m1;	// 求 lcm(m1, m2)
    	}
    	return (r1 % m1 + m1) % m1;
    }
    
    int main()
    {
    	long long a1, a2;
    	scanf("%d", &n);
    	for(int i = 1; i <= n; ++i)
    	{
    		scanf("%lld%lld", &a1, &a2);
    		m[i] = a1, r[i] = a2;
    	}
    	ll ans = exCRT(m, r, n);
    	printf("%lld\n", (long long)ans);
    	return 0;
    }