补全：累加初值

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

补全 crt：累加器 x 从 0 开始。补全后解三个方程 x≡2 (mod 3)、x≡3 (mod 5)、x≡2 (mod 7)。

本节模型：crt(rs, ms) 模数两两互质时，把每个方程的贡献 rs[i]·Mi·(Mi 的逆元) 加起来。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 补全：乘上 Mi 的逆元矩阵快速幂加速什么 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long exgcd(long long a, long long b, long long& x, long long& y) {
    // 扩展欧几里得：返回 g = gcd(a, b)，并求出 a*x + b*y = g 的一组 x、y
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long inv_ex(long long a, long long p) {
    // 用 exgcd 求 a 关于 p 的逆元（要求 gcd(a, p) = 1）
    long long x, y;
    exgcd(a % p, p, x, y);
    return (x % p + p) % p;
}

long long crt(const vector<long long>& rs, const vector<long long>& ms) {
    // 中国剩余定理：模数两两互质，返回同时满足 x % ms[i] == rs[i] 的最小非负 x
    long long M = 1;
    for (long long m : ms) M *= m;
    long long x = 1;  // TODO: 累加器应该从 0 开始
    for (size_t i = 0; i < rs.size(); i++) {
        long long Mi = M / ms[i];
        x = (x + rs[i] * Mi % M * inv_ex(Mi % ms[i], ms[i])) % M;
    }
    return x;
}

int main() {
    cout << crt({2, 3, 2}, {3, 5, 7}) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

补全：累加初值

更多题目

全部评论