扩展中国剩余定理

中国剩余定理可以用来求解下面的线性同余方程组 $\left\{\begin{array}{c} x \equiv r_{1}\left(\bmod m_{1}\right) \\ x \equiv r_{2}\left(\bmod m_{2}\right) \\ \vdots \\ x \equiv r_{n}\left(\bmod m_{n}\right) \end{array}\right.$ $其中模数 m_{1}, m_{2}, \cdots, m_{n} 为两两互质的整数, 求 x 的最小非负整数解。$ 做法如下：

1. 计算所有的模数的积为M
2. 计算第i个方程的$c_i=\frac{M}{m_i}$
3. 求$c_i$再模$m_i$下的逆元$c_i^{-1}$
4. $x=\sum_{i=1}^{n}{r_ic_ic_i^{-1}}(\bmod M)$

扩展中国剩余定理：

模数不一定互质 思路： 先考虑2个式子：$x\equiv m_1(\bmod a_1),x\equiv m_2(\bmod a_2)$ 等价变形得:$x=k_1*a_1+m1,x=k_2*a_2+m2,$ 则：$k_1*a_1+m_1=k_2*a_2+m_2$ 移项得$k_1*a_1-k_2*a_2=m_2-m_1$

扩展欧几里得算法： 用来求$ax+by=gcd(a,b)$的一组整数解 当$b=0$时，显然$x=1,y=0$是一组解 当$b\neq0$时， $\begin{aligned} \operatorname{gcd}(a, b) & =a x+b y \\ \operatorname{gcd}(b, a \% b) & =b x_{1}+(a \% b) y_{1} \\ & =b x_{1}+\left(a-\left\lfloor\frac{a}{b}\right\rfloor \times b\right) y_{1} \\ & =a y_{1}+b\left(x_{1}-\frac{a}{b} y_{1}\right) \end{aligned}$ 所以:$x=y_{1}, y=x_{1}-\frac{a}{b} y_{1}$ 通解： $\left\{\begin{array}{l} x=x_{0}+\frac{b}{\operatorname{gcd}(a, b)} * k \\ y=y_{0}-\frac{a}{\operatorname{gcd}(a, b)} * k \end{array}\right.( 考虑 a x+b y=0 构造 )$

求不定方程$ax+by=c$的一组整数解： 如果$gcd(a,b)|c$,一定有整数解，否则没有 可以先用扩展欧几里得算法求出$ax+by=gcd(a,b)$的一组解，在乘以$\frac{c}{gcd(a,b)}$，即可得到原方程的特解。

因此上式的$k_1*a_1-k_2*a_2=m_2-m_1$ 可以看成$\left\{\begin{array}{l} a_1*k_1+(-a_2)*k_2=m_2-m_1\\ a*x+b*y=c \end{array}\right.$ 有解与无解的判定：如果$gcd(a,b)|c$,一定有整数解，否则没有 如果有解：使用扩展欧几里得算法求出对应的解为$k_1$,再将其扩大$\frac{m_2-m_1}{d}$倍 则通解$x=k_1+\frac{a_2}{d}*k$，因为要求最小的$x$,可以使用$x=(x\%t+t)\%t$求出，其中$t=\frac{a_2}{d}$ 接着考虑将一开始选择的两个式子进行合并：$x=k_1*a_1+m1$,$k$是满足方程的最小整数 带入求出的$k_1$，则$x=a_1*(k_1+\frac{a_2}{d}*k)+m_1$ 即$x=\frac{a_1*a_2}{d}*k+a_1*k_1+m_1$ 可以看成一个新的方程$x=a*k+m$ 其中a=\frac{a_1*a_2}{d}$$m=a_1*k_1+m_1

代码

/**
⠀⠀⠀⠀⠰⢷⢿⠄
⠀⠀⠀⠀⠀⣼⣷⣄
⠀⠀⣤⣿⣇⣿⣿⣧⣿⡄
⢴⠾⠋⠀⠀⠻⣿⣷⣿⣿⡀
0   ⠀⢀⣿⣿⡿⢿⠈⣿
⠀⠀⠀⢠⣿⡿⠁⠀⡊⠀⠙
⠀⠀⠀⢿⣿⠀⠀⠹⣿
⠀⠀⠀⠀⠹⣷⡀⠀⣿⡄
⠀⠀⠀⠀⣀⣼⣿⠀⢈⣧
*/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define ct(x) cout<<x<<" ";
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

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() {
    //IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    int n;
    cin >> n;
    bool flag = true;
    ll a1, m1;
    cin >> a1 >> m1;
    for (int i = 0; i < n - 1; i++) {
        ll a2, m2;
        cin >> a2 >> m2;
        ll x, y;
        ll d = exgcd(a1, a2, x, y);
        if ((m2 - m1) % d)//不能整除则无解
        {
            flag = false;
            break;
        }
        //此时的x,y为 a1x+a2y=gcd(a1,a2)=d的解，需要扩大
        x *= (m2 - m1) / d;
        //通解为:x =x0+a2/d*k;x0为上面求出来的特解
        ll t = a2 / d;
        x = (x % t + t) % t;

        //将两组合并,这里得先变m1，因为m1里面包含了a1，如果
        //先变a1会影响m1
        m1 = a1 * x + m1;
        a1 = abs(a1 / d * a2);
    }

    if (flag) {
        pr((m1 % a1 + a1) % a1)
    } else {
        pr(-1)
    }


    return 0;
}