扩展剩余定理

#include <iostream>
using namespace std;
const int N = 100 ;
typedef long long ll ;
ll m[N] , c[N] ;
ll exgcd(ll a , ll b , ll &x , ll &y)
{
	if(b == 0)
	 {
	 	x = 1 , y = 0 ;
	 	return a ;
	 }
	 ll t = exgcd(b , a % b , y , x) ;
	 y -= a / b * x ;
	 return t ;
}
ll inv(ll a , ll b)
{
	ll x , y ;
	ll t = exgcd(a , b , x , y) ;
	while(x < 0) x += b ;
	return x ; 
}
ll gcd(ll a , ll b)
{
	return b == 0 ? a : gcd(b , a % b) ;
}
void solve()
{
	ll k ;
	cin >> k ;
	for(int i = 1 ;i <= k ;i ++) scanf("%lld%lld" , &m[i] , &c[i]) ;
	bool flag = true ;
	for(int i = 2 ;i <= k ;i ++)
	{
		ll m1 = m[i - 1] , c1 = c[i - 1] , m2 = m[i] , c2 = c[i] ;
		ll d = gcd(m1 , m2) ;
		if((c2 - c1) % d) {	flag = 0 ;break ;	}
		m[i] = m1 * m2 / d ;
		c[i] = (inv(m1 / d , m2 / d) * (c2 - c1) / d ) % (m2 / d) * m1 + c1 ;
		c[i] = (c[i] % m[i] + m[i]) % m[i] ;
	}
	printf("%lld
" ,flag ?  c[k] : -1 ) ;
}
int main()
{
	solve() ;
	return 0 ;
}