blob: 623f94b50a8294d2268eb69043abdd38dc6817ba (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
// Laufzeit: O(n * log(n)), n := Anzahl der Kongruenzen. Nur für
// teilerfremde Moduli. Berechnet das kleinste, nicht negative x,
// das alle Kongruenzen simultan löst. Alle Lösungen sind
// kongruent zum kgV der Moduli (Produkt, da teilerfremd).
struct ChineseRemainder {
using lll = __int128;
vector<lll> lhs, rhs, mods, inv;
lll M; // Produkt über die Moduli. Kann leicht überlaufen.
ll g(const vector<lll> &vec) {
lll res = 0;
for (int i = 0; i < sz(vec); i++) {
res += (vec[i] * inv[i]) % M;
res %= M;
}
return res;
}
// Fügt Kongruenz l * x = r (mod m) hinzu.
void addEquation(ll l, ll r, ll m) {
lhs.push_back(l);
rhs.push_back(r);
mods.push_back(m);
}
ll solve() { // Löst das System.
M = accumulate(all(mods), lll(1), multiplies<lll>());
inv.resize(sz(lhs));
for (int i = 0; i < sz(lhs); i++) {
lll x = (M / mods[i]) % mods[i];
inv[i] = (multInv(x, mods[i]) * (M / mods[i]));
}
return (multInv(g(lhs), M) * g(rhs)) % M;
}
};
|
