excrt

xiezheyuan · 2023-10-17 11:14:06 · 算法·理论

前言

ExCRT 用于求出不保证模数互质的同余方程组的解。

不知道 ExCRT 这个名字是谁起的，反正跟 CRT 没有关系。

思路

ExCRT 的思想是两个同余方程的合并。也就是说对于下面两个同余方程：

可以将其合并成一个同余方程 x\equiv b\pmod{a}。然后可以重复这一过程知道将整个方程组合并成一个方程（学名 reduce），然后易得解。

首先考虑同余的意义 0\leq m\lt n,x\equiv m\pmod{n}\Leftrightarrow \exists k\in\mathbb{Z},x=nk+m。

我们可以取两个整数 k_1,k_2，使得：

移项，得：

这是一个标准的关于 k_1,k_2 的二元一次丢番图方程。根据裴蜀定理，该方程有解的充要条件为：

假设方程有解，则不妨将原方程两边同时约去 d=\frac{b_2-b_1}{\gcd(a_1,a_2)}。

则有：

可以看成一个关于 \frac{k_1}{d},\frac{-k_2}{d} 的二元一次不定方程，可以使用 exgcd 求出一组 k_1,k_2。

然后则有：

我们可以取：

作为合并后的同余方程。至于 k_2，因为它是负数所以处理较为麻烦。

注：如果 d=0 怎么办？实际上也是对的。

如果 d=0，则 b_1=b_2，按照上述方法算出来 x\equiv b_1\pmod{\text{lcm}(a_1,a_2)}。容易发现这是正确的。

时间复杂度 O(n\log V) 其中 n 为方程组数量 V 为值域。

参考实现

P4777

#include <bits/stdc++.h>
#define int __int128
using namespace std;

const int N = 1e5+5;

void exgcd(int a,int b,int &x,int &y){
    if(!b) x = 1, y = 0;
    else exgcd(b, a%b, y, x), y -= a/b * x;
}

struct Equation{
    long long a,b;// x=b(mod a)
};

queue<Equation> st;
long long n;

void excrt(){
    if(st.size() <= 1) return;
    Equation eq1 = st.front(); st.pop();
    Equation eq2 = st.front(); st.pop();
    int a = eq1.a, b = eq1.b, A = eq2.a, B = eq2.b;
    int g = __gcd(a,A);
    if((B - b) % g > 0){
        cout<<-1;
        exit(0);
    }
    int d = (B - b) / g;
    int k1,k2;
    exgcd(a,A,k1,k2);
    k1 = (k1 * d);
    int x = k1 * a + b, y = (a * A) / g;
    x = (x % y + y) % y;
    st.push({(long long)y, (long long)x});
    excrt();
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        long long x,y;
        cin>>x>>y;
        st.push({x,y});
    }
    excrt();
    Equation top = st.front();
    cout<<top.b;
    return 0;
}