From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- math/chineseRemainder.cpp | 18 ++++++++++-------- 1 file changed, 10 insertions(+), 8 deletions(-) (limited to 'math/chineseRemainder.cpp') 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 lhs, rhs, mods, inv; lll M; // Produkt über die Moduli. Kann leicht überlaufen. ll g(vector &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()); - inv.resize(lhs.size()); - for (int i = 0; i < (int)lhs.size(); i++) { + M = accumulate(mods.begin(), mods.end(), lll(1), + multiplies()); + 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])); } -- cgit v1.2.3