diff options
Diffstat (limited to 'math/chineseRemainder.cpp')
| -rw-r--r-- | math/chineseRemainder.cpp | 18 |
1 files changed, 9 insertions, 9 deletions
diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index 2cf12f7..ac1b71e 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,10 +1,10 @@ // Laufzeit: O(n * log(n)), n := Anzahl der Kongruenzen -// Nur für teilerfremde Moduli. -// Berechnet das kleinste, nicht negative x, das die Kongruenzen simultan löst. -// Alle Lösungen sind kongruent zum kgV der Moduli (Produkt, falls alle teilerfremd sind). +// 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). struct ChineseRemainder { typedef __int128 lll; - vector<lll> lhs, rhs, module, inv; + vector<lll> lhs, rhs, mods, inv; lll M; // Produkt über die Moduli. Kann leicht überlaufen. ll g(vector<lll> &vec) { @@ -20,17 +20,17 @@ struct ChineseRemainder { void addEquation(ll l, ll r, ll m) { lhs.push_back(l); rhs.push_back(r); - module.push_back(m); + mods.push_back(m); } // Löst das System. ll solve() { - M = accumulate(module.begin(), module.end(), lll(1), multiplies<lll>()); + M = accumulate(mods.begin(), mods.end(), lll(1), multiplies<lll>()); inv.resize(lhs.size()); for (int i = 0; i < (int)lhs.size(); i++) { - lll x = (M / module[i]) % module[i]; - inv[i] = (multInvers(x, module[i]) * (M / module[i])); + lll x = (M / mods[i]) % mods[i]; + inv[i] = (multInv(x, mods[i]) * (M / mods[i])); } - return (multInvers(g(lhs), M) * g(rhs)) % M; + return (multInv(g(lhs), M) * g(rhs)) % M; } }; |