Chinese Remainder Theorem - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct Congruence {
    ll a, m;
};

const int N = 2e5+7;
int phi[N];

ll fast_pow(ll a, ll b, ll mod) {
    ll ans = 1;
    while (b > 0) {
        if (b & 1)
            ans = (ans*a)%mod;
        a = (a*a)%mod;
        b/= 2;
    }
    return ans;
}

ll mod_inv(ll a, ll mod) {
    return fast_pow(a, phi[mod]-1, mod);
}

Congruence chinese_remainder_theorem(vector<Congruence> const& congruences) {
    ll M = 1;
    for (auto const& congruence : congruences) {
        M *= congruence.m;
    }
    ll solution = 0;
    for (auto const& congruence : congruences) {
        ll a_i = congruence.a;
        ll M_i = M / congruence.m;
        ll N_i = mod_inv(M_i, congruence.m);
        solution = (solution + a_i * M_i % M * N_i) % M;
    }
    return {solution, M};
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    for (int i = 0; i < N; i++)
        phi[i] = i;
    for (int i = 1; i < N; i++) {
        for (int j = 2 * i; j < N; j += i) {
            phi[j] -= phi[i];
        }
    }
}