视频

【表达整数的奇怪形式】 https://www.bilibili.com/video/BV1aq66Y3Eiw/?share_source=copy_web&vd_source=6a3494b432f4f0cd85b8778d3e41c95f

题目描述

204 表达整数的奇怪方式
求简单同余方程组,即求x使得
$$\begin{array}{l} \left\{\begin{matrix} x \equiv m_{1} \bmod a_{1} \quad \text{①} \\ x \equiv m_{2} \bmod a_{2} \quad \text{②} \\ x \equiv m_{3} \bmod a_{3} \quad \text{③} \\ \end{matrix}\right. \end{array} $$
上式等价为
$$\begin{array}{l} \left\{\begin{matrix} x = m_{1} + k_{1} * a_{1} \quad \text{①’} \\ x = m_{2} + k_{2} * a_{2} \quad \text{②’} \\ x = m_{3} + k_{3} * a_{3} \quad \text{③’} \\ \end{matrix}\right. \end{array} $$
其中$k_{i}$为未知整数

求解方法，任选两个方程，将其合并为一个，不断迭代，最终将多个方程，合并为一个方程。
合并方法，联立方程 ①’和 ②’ ，得
$$\begin{array}{l} m_{1} + k_{1} * a_{1} = m_{2} + k_{2} * a_{2}\\ k_{1} * a_{1} - k_{2} * a_{2}= m_{2} - m_{1}\\ k_{1} * a_{1} + (-k_{2}) * a_{2}= m_{2} - m_{1}\\ \end{array} $$
使用扩展欧几里得算法解得 $k_{1}$ 和 $-k_{2}$ 的一组特解。
同时，可以轻松得到其通解为
$$\begin{array}{l} \left\{\begin{matrix} k_{1} = k_{1特} + K * a_{2}/(a_{1},a_{2}) \\ -k_{2} = -k_{2特} - K * a_{1}/(a_{1},a_{2}) \\ \end{matrix}\right. \end{array} $$
其中，K此时为任意整数。
此时将$k_{1}$的通解带回①’，得
$$\begin{array}{l} x = m_{1} + k_{1} * a_{1}\\ x = m_{1} + [k_{1特} + K * a_{2}/(a_{1},a_{2})] * a_{1}\\ x = (k_{1特} * a_{1} + m_{1}) + K * (a_{2}/(a_{1},a_{2}) * a_{1}) \\ x = m_{新} + K * a_{新} \quad \text{④’}\\ \end{array} $$
再将 ④’ 和 ③’ 联立得
$$\begin{array}{l} m_{新} + K * a_{新} = m_{3} + k_{3} * a_{3}\\ \end{array} $$
其中，K此时为未知整数。

样例

#include <iostream>
#include <cstring>
#include <algorithm>

typedef long long LL;



using namespace std;

LL exgcd(LL a, LL b, LL &x, LL &y)  // 扩展欧几里得算法, 求x, y，使得ax + by = gcd(a, b)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

LL positive_mod(LL a,LL b){
    return ( a % b + b ) % b;
}



int main()
{
    int n;
    cin>>n;
    LL a1,m1;
    LL ai,mi;
    cin >> a1 >> m1;
    LL k1,ki;
    for (int i = 2; i <= n; i ++ ){
        cin >> ai >> mi;
        LL d = exgcd(a1,ai,k1,ki);
        ki=-ki;

        if( (mi-m1)%d!=0 ){
            cout << -1;
            return 0;
        }

        k1*=(mi-m1)/d;
        k1=k1%(ai/d);//防止溢出
        m1=(m1+k1*a1)%(a1/d*ai);//防止溢出
        a1=a1/d*ai;

    }
    cout << positive_mod(m1,a1);//答案要正数
}