扩展中国剩余定理（exCRT）

我 tm……CRT 没看懂 exCRT 却看懂了……emmmm……
而且这名字完全就是国内的 OI 带师胡起的吧……

---

考虑一次同余方程组

[egin{cases} x equiv a_1 ({ m mod} m_1) \ xequiv a_2 ({ m mod} m_2) \ ... \ x equiv a_n ({ m mod} m_n)end{cases} ]

的解的问题。
CRT 成立的前提是 (gcd{m_n}=1)。这里不一定保证这个条件。
原理还是很简单的，利用归纳法，考虑前 (k-1) 个方程组的解为 (x)，并记 (m={ m lcm}(m_1,dots,m_{k-1}))，那么对于第 (k) 个方程，就是找一个 (tinmathbb{Z})，使得 (x+tmequiv a_kpmod{m_k})。把 (x) 扔到右边就是一个 (tmequiv a_k-xpmod{m_k})，可以用 exgcd 求了。
所以纵观整个算法其实是一个不断用 exgcd 迭代的过程。
好，理论说完了，来到毒瘤代码环节……这玩意……真心没办法言传……我看了好久才会orz……
把关键部分注释一下（它咕了

int main()
{
    scanf("%d",&n);
    ll M,ans,x,y; scanf("%lld%lld",&M,&ans);
    for(int i=1;i<n;++i)
    {
        ll mt,at; scanf("%lld%lld",&mt,&at);
        ll c=((at-ans)%mt+mt)%mt;
        ll gcd=exgcd(M,mt,x,y);
        if(c%gcd!=0) {puts("-1"); return 0;}
        x=smul(x,c/gcd,mt);
        ans+=x*M; M*=mt/gcd;
        ans=(ans+M)%M;
    }
    printf("%lld",ans);
    return 0;
}