数论 · 扩展中国剩余定理（EXCRT）

pldzy · 2021-12-10 14:04:02 · 个人记录

问题

已知有：

在m 数组的数两两不一定不互质的情况下，求 x 的最小非负整数解。

求解

假设我们已经求解出了前 (k-1) 个方程的解为 x，且有 M 为 LCM_{i = 1}^{k-1} m_i。

此时易知前 k 个方程的通解就是 x + t* M（t 为整）。

现在我们要求解一个 t'，使得 x + t' * M \equiv a_k \pmod {m_k}。

转换一下就是 m_k * r +t' * M = a_k - x。

exgcd无处不在！！

假设我们现在用扩欧几里得求解方程 a'x+b'y=c'，

那么 a'=m_k,\ b'=M,\ c'=a_k-x。

然后我们解得 x_0 满足 a'x+b'y=\gcd(a',b')。

转化一下：x_j=x_0 * c' / \gcd(a',b')。

这样我们就有一个解 x_j（也就是上柿的 r），要求 x_{min}。

详情请戳 ->《数论 · 求解线性同余方程》

设 t=\dfrac{b'}{\gcd(a',b')}，就有 x_{min}=(x_j \% t+t)\%t。

然后再把它统计到 x 中，这样 x 就是满足前 k 个方程的解了。

别忘了也统计到 M 里面去。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define int long long
#define rint register int
#define fo(i, a, b) for(rint i (a); i <= b; ++i)
const int maxn = 1e5 + 5;

int n, a[maxn], m[maxn];
int x, y;

inline int read ()
{
    int x = 1, s = 0;
    char ch = getchar ();
    while (ch < '0' or ch > '9') {if (ch == '-') x = -1; ch = getchar ();}
    while (ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar ();
    return x * s;
}

inline int exgcd (int a, int b)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int res = exgcd (b, a % b);
    int tmp = x;
    x = y, y = tmp - a / b * y;
    return res;
}

inline int pmul (int x, int p, int mod)
{
    int res = 0;
    while (p >= 1)
    {
        if (p & 1)
            res = (res + x) % mod, p -= 1;
        p /= 2, x = (x + x) % mod;
    }
    return res;
}

int M, ans;

inline int excrt ()
{
    M = m[1], ans = a[1];
    fo (i, 2, n)
    {
        int a_ = M, b_ = m[i], c_ = (a[i] - ans % b_ + b_) % b_;
        int gcd = exgcd (a_, b_), bg = b_ / gcd;
        x = pmul (x, c_ / gcd, bg);
        ans = ans + x * M;
        M *= bg, ans = (ans % M + M) % M;
    }
    return ans;
}

signed main ()
{
    n = read ();
    fo (i, 1, n) 
        m[i] = read (), a[i] = read ();
    printf ("%lld\n", excrt ());    
    return 0;
}

——End——