扩展中国剩余定理(EXCRT)

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

对于每一个$x≡ b_1(\mod a_1)$,可以设k为$x/a_1$的商，易得$a_n*k_n+b_n=x$。
对于前两个式子

$$\begin{cases} a_1*k_1+b_1=x \\ a_2*k_2+b_2=x \end{cases}$$

可得$a_1*k_1+b_1=a_2*k_2+b_2$
即$a_1*k_1-a_2*k_2=b_2-b_1$
通过扩展欧几里得算法，不难算出$k_1,k_2$的所有解为

$$\begin{cases} k_1+k*\frac{a2}{d} \\ k_2+k*\frac{a1}{d} \end{cases}$$

（代入原式即可看出）
对于每个$k_1,k_2$取最小（避免爆long long）可得
$k_1=(k_1\mod t+t)\mod t$

$t=a_2/d$

由于扩展欧几里得求出的$k_1,k_2$是满足$a_1*k_1-a_2*k_2=d$(d为$a_1,a_2$的最大公约数)

要满足$a_1*k_1-a_2*k_2=m_2-m_1$,就让$k_1$再乘上$\frac{b_2-b_1}{d}$,

此时,再将k1
代入原式得

$a_1*(k1+k*\frac{a_1*a_2} {d})+b_1=x=a_1*k_1+b_1+k*\frac{a_1*a_2}{d}$

设$x_0=a_1*k_1+b_1,a=\frac{a_1*a_2}{d}$
可得$k*a+x_0=x$

仔细观察发现与上面的式子出乎意料的一样,所以我们就可以反复重复上述操作,将所有式子最终合并为一个式子,最后$x=(x_0\%a+a)\%a$

需要注意的是这到题可能会再乘法的时候爆long long,所以需要用到快速乘
龟速乘(或者__int128)
代码如下

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;

inline ll mul(ll a, ll b, ll m)
{
    ll c = a*b-(ll)((long double)a*b/m+0.5)*m;
    return c<0 ? c+m : c; //a*b%m
}

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    bool is = true;
    ll n;
    scanf("%lld", &n);
    ll a1, m1;
    scanf("%lld%lld", &a1, &m1);
    for (int i = 1; i < n;i++)
    {
        ll ai, mi, k1, ki;
        scanf("%lld%lld", &ai, &mi);
        ll d = exgcd(a1, ai, k1, ki);
        if((mi-m1)%d)
        {
            is = false;
            break;
        }         
        ll t = ai / d;
        k1 = mul(k1, (mi - m1) / d, t );
        k1 = (k1 % t + t) % t;
        m1 = a1 * k1 + m1;
        a1 = abs(ai / d * a1);
    }
    if(is)
        printf("%lld", (m1 % a1 + a1) % a1);
    else
        printf("-1");
}