Strange Way to Express Integers

  拓展中国剩余定理的模板题，但我并看不懂模板OTZ(过段时间会补上个人理解，先把代码放这)

#include <cstdio> 
#include <iostream> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
#include <vector>
#include <list>
#include <string>
#include <queue>
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e6+5;
ll exgcd(ll a,ll b,ll& x,ll& y)
{
    if(!b)
    {
        x=1;y=0;
        return a;
    }
    ll r=exgcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-(a/b)*y;
    return r;
}
ll a[maxn],m[maxn];
ll solve(ll n)
{
    ll M=m[1];
    ll ans=a[1];
    ll x,y;ll r;ll tmp;
    for(int i=2;i<=n;i++)
    {
        r=exgcd(M,m[i],x,y);
        if((a[i]-ans)%r)
            return -1;
        x*=(a[i]-ans)/r;
        tmp=m[i]/r;
        x=(x%tmp+tmp)%tmp;
        ans=M*x+ans;
        M=M/r*m[i];
        ans%=M;
    }
    ans=(ans%M+M)%M;
    return ans;
}
int main()
{    
    ll k;
    while(cin>>k)
    {
        for(int i=1;i<=k;i++)
        cin>>m[i]>>a[i];
        ll ans=solve(k);
        cout<<ans<<endl;
    }
    return 0;
}