解一组同余方程

运行下面这段程序：

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

#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 = 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}, {3, 5}) << endl;
}

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