diff options
Diffstat (limited to 'math/chineseRemainder.cpp')
| -rw-r--r-- | math/chineseRemainder.cpp | 14 |
1 files changed, 6 insertions, 8 deletions
diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index 86a10ae..623f94b 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,14 +1,13 @@ -// 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, falls alle teilerfremd sind). +// 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(vector<lll> &vec) { + ll g(const vector<lll> &vec) { lll res = 0; for (int i = 0; i < sz(vec); i++) { res += (vec[i] * inv[i]) % M; @@ -24,8 +23,7 @@ struct ChineseRemainder { mods.push_back(m); } - // Löst das System. - ll solve() { + 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++) { |