综合补全：CRT 模数乘积

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

补全 crt：M 是模数乘积。补全后解 x≡3 (mod 5)、x≡4 (mod 7)。

综合：把逆元、组合数、CRT、矩阵快速幂按题目组合起来用。

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

提交你的答案

请登录后提交答案。

去登录

← 综合补全：组合数分母综合补全：转移矩阵 →

更多题目

代码编辑器

语言： 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;  // TODO: 模数要相乘
    long long x = 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({3, 4}, {5, 7}) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

综合补全：CRT 模数乘积

更多题目

全部评论