diff options
Diffstat (limited to 'math/chineseRemainder.cpp')
| -rw-r--r-- | math/chineseRemainder.cpp | 18 |
1 files changed, 10 insertions, 8 deletions
diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index ac1b71e..2308836 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,15 +1,16 @@ // 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). +// 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; + using lll = __int128; vector<lll> lhs, rhs, mods, inv; lll M; // Produkt über die Moduli. Kann leicht überlaufen. ll g(vector<lll> &vec) { lll res = 0; - for (int i = 0; i < (int)vec.size(); i++) { + for (int i = 0; i < sz(vec); i++) { res += (vec[i] * inv[i]) % M; res %= M; } @@ -25,9 +26,10 @@ struct ChineseRemainder { // Löst das System. ll solve() { - M = accumulate(mods.begin(), mods.end(), lll(1), multiplies<lll>()); - inv.resize(lhs.size()); - for (int i = 0; i < (int)lhs.size(); i++) { + M = accumulate(mods.begin(), mods.end(), 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])); } |