[lnsyoj517/luoguP4777]扩展中国剩余定理

标签：luoguP4777 方程 pmod 定理 int lnsyoj517 include LL equiv

题意

原题链接
求线性同余方程组

\[\begin{cases}x\equiv b_1\pmod{a_1}\\x\equiv b_2\pmod{a_2}\\\dots\\x\equiv b_n\pmod{a_n}\end{cases} \]

的最小非负整数解。

sol

与[lnsyoj163/luoguP1495]曹冲养猪不同的是，本题无法保证互质，这就导致中国剩余定理无法使用，需要一种新的方式来解决问题。
我们思考：如果我们可以将两个方程合并为一个方程，那么整个方程组都可以合成为一个方程，问题也就解决。
下面进行推导：
对于两个方程 \(x\equiv b_1\pmod{a_1}\)、\(x\equiv b_2\pmod{a_2}\)，，我们将其分别转换为 \(x + a_1p = b_1\) 和 \(x + a_2q = b_2\)，整理得 \(a_2q-a_1p = b_2 - b_1\)，利用扩展欧几里得算法，我们可以求出一组可行解 \(p, q\)。此时，新的方程的 \(b\) 即为原来的 \(b + a_1p\)，新的方程的 \(a\) 即为原来的 \(a_1,a_2\) 的最大公倍数。
最终，合并成的一个方程，其 \(b\) 的值即为最终答案.
注意：勤取模

代码

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

using namespace std;
typedef long long LL;

const int N = 100005;

int n;
LL a[N], m[N];

LL exgcd(LL a, LL b, __int128 &x, __int128 &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(){
    while (scanf("%d", &n) != EOF){
        for (int i = 1; i <= n; i ++ ) scanf("%lld%lld", &m[i], &a[i]);
        LL b = a[1];
        __int128 M = m[1];
        bool flag = false;
        for (int i = 2; i <= n; i ++ ){
            __int128 p, q;
            LL d = exgcd(M, m[i], p, q);
            if (((a[i] - b % m[i] + m[i]) % m[i]) % d) {
                flag = true;
                puts("-1");
                break;
            }
            __int128 u = 1;
            p = u * p * ((a[i] - b % m[i] + m[i]) % m[i]) / d;
            LL t = abs(m[i] / d);
            p = (p % t + t) % t;
            LL m1 = M;
            M = M / d * m[i];
            b = ((u * m1 * p % M + b % M) % M + M) % M;
        }
        if (flag) continue;
        printf("%lld\n", b);
    }
    return 0;
}

标签：luoguP4777,方程,pmod,定理,int,lnsyoj517,include,LL,equiv
From： https://www.cnblogs.com/XiaoJuRuoUP/p/-/lnsyoj517_luoguP4777