blob: ccbc5dc5cfe2e220094062f5ca0115910a7450e3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
struct CRT {
using lll = __int128;
lll M = 1, sol = 0; // Solution unique modulo M
bool hasSol = true;
// Adds congruence x = a (mod m)
void add(ll a, ll m) {
auto [d, s, t] = extendedEuclid(M, m);
if((a - sol) % d != 0) hasSol = false;
lll z = M/d * s;
M *= m/d;
sol = (z % M * (a-sol) % M + sol + M) % M;
}
};
|
