中国剩余定理

求解模线性方程组。

\begin{aligned} {\begin{cases} x_{1} \equiv a_{1} (\mod r_{1}) \\ x_{2} \equiv a_{2} (\mod r_{2}) \\ \dots \\ x_{k} \equiv a_{k} (\mod r_{k}) \end{cases} \end{aligned}

crt

当 $r_{1}, r_{2}, \dots, r_{k}$ 为互质的，设 $M = \prod_{i = 1}^{k} r_{i}, A_{i} = \frac{M}{r_{i}}$ ，可的 $M$ 是 $r_{1}, \dots, r_{k}$ 的 lcm

可得 $A_{i}, r_{i}$ 是互质的，则必存在 $A_{i}$ 模 $r_{i}$ 意义下的逆元 $t_{i}$ 使得 $A_{i} t_{i} \equiv 1 (\mod r_{i})$

解 $x_{i} = a_{i} A_{i} t_{i}$ 是满足第 $i$ 个方程的。同时 $\forall j \neq i$ ，都有 $x_{i} \equiv 0 (\mod r_{j})$ ，因为 $A_{i}$ 中有一个因子 $r_{j}$

可以得到通解 $x = \sum_{i = 1}^{k} a_{i} A_{i} t_{i} + p M (p \in Z)$ 。显然满足条件


#include 
using namespace std;
typedef unsigned long long uLL;
typedef long double LD;
typedef long long LL;
typedef double db;
const int N = 55;
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) return x = 1, y = 0, a;
    register LL gcd = exgcd(b, a % b, y, x);
    return y -= a / b * x, gcd;
}
inline LL inv(LL a, LL b) {
    register LL x, y;
    exgcd(a, b, x, y);
    return (x % b + b) % b;
}
int n;
LL a[N], r[N], mul = 1, A[N], ans;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &r[i], &a[i]), mul *= r[i];
    for (int i = 1; i <= n; i++) {
        A[i] = mul / r[i];
        ans += a[i] * A[i] * inv(A[i], r[i]);
    }
    printf("%lld", ans % mul);
}

excrt

当 $r_{1}, \dots, r_{k}$ 不互质，此时使用扩展 crt

\begin{aligned} {\begin{cases} x_{1} \equiv a_{1} (\mod r_{1}) \\ x_{2} \equiv a_{2} (\mod r_{2}) \\ \dots \\ x_{k} \equiv a_{k} (\mod r_{k}) \end{cases} \end{aligned}

看前两个方程。

$x = k \cdot r_{1} + a_{1} = p \cdot r_{2} + a_{2}$ ，其中 $k, p \in Z$

$k \cdot r_{1} - p \cdot r_{2} = a_{2} - a_{1}$ ，这是形如 $a x + b y = c$ 的形式，用 exgcd 求解。

此处可得 $gcd (r_{1}, r_{2}) ∤ (a_{2} - a_{1})$ 时无解。

求出一个解 $k_{0}$ ，则通解 $k = k_{0} + o * \frac{r_{2}}{gcd (r_{1}, r_{2})} (o \in Z)$

将 $k$ 带入 $k \cdot r_{1} + a_{1}$ 可得

(k_{0} + o * \frac{r_{2}}{gcd (r_{1}, r_{2})}) \cdot r_{1} + a_{1} = k_{0} * r_{1} + a_{1} + o * lcm (r_{1}, r_{2})

即 $x \equiv k_{0} * r_{1} + a_{1} (\mod lcm (r_{1}, r_{2}))$

相当于合并了两个方程，合并 $n - 1$ 次即可得到答案。

注意 $k_{0}$ 应乘上 $\frac{a_{2} - a_{1}}{gcd (r_{1}, r_{2})}$

模板题需要用龟速乘。


#include 
using namespace std;
typedef unsigned long long uLL;
typedef long double LD;
typedef long long LL;
typedef double db;
const int N = 100005;
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) return x = 1, y = 0, a;
    register LL gcd = exgcd(b, a % b, y, x);
    return y -= a / b * x, gcd;
}
LL G;
inline LL mul(LL x, LL y, LL p) {
    return (x * y - (LL)((LD)x / p * y) * p + p) % p;
}
inline bool sol(LL a, LL b, LL c, LL &x, LL &y) {
    G = exgcd(a, b, x, y);
    register LL t;
    if (c % G) return false;
    t = b / G;
    x = mul(x, c / G, t);
    x = (x + t) % t;
    y = (c - a * x) / b;
    return true;
}
int n, isL;
LL a[N], r[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &r[i], &a[i]);
    isL = 1;
    for (int i = 1; i < n; i++) {
        register LL x, y;
        if (!sol(r[i], r[i + 1], a[i + 1] - a[i], x, y)) {
            isL = 0; break;
        }
        a[i + 1] = x * r[i] + a[i];
        r[i + 1] = r[i] / G * r[i + 1];
    }
    printf("%lld", a[n]);
}

相关阅读:
数学建模——最大流问题（配合例子说明）
计算机网络笔记第三章数据链路层
零基础非计算机专业转行软件测试可行吗？
MySQL锁
MAC 通过IDEA启动tomcat，显示80端口被占用解决办法
JWT原理
知识分享钡铼网关功能介绍：使用SSLTLS 加密，保证MQTT通信安全
不做工程等于纸上谈兵——对话OceanBase创始人阳振坤
Jmeter---非GUI命令行的执行生成报告、使用ant插件执行接口测试脚本生成报告
Facebook又双叒崩了！网友：扎克伯格一周只用上三天班？

原文地址：https://blog.csdn.net/KonjakuLAF/article/details/126237492