From 36e9961fe1f3a63693c86da020cf2c38893170b9 Mon Sep 17 00:00:00 2001 From: Lucas Schwebler Date: Wed, 13 Mar 2024 22:21:49 +0100 Subject: new crt --- math/chineseRemainder.cpp | 47 +++++++++++++---------------------------------- 1 file changed, 13 insertions(+), 34 deletions(-) (limited to 'math') diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index 623f94b..a1aa480 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,35 +1,14 @@ -// 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 lhs, rhs, mods, inv; - lll M; // Produkt über die Moduli. Kann leicht überlaufen. +struct CRT{ + using lll = __int128_t; + lll M = 1, sol = 0; // Solution unique modulo M + bool hasSol = true; - ll g(const vector &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()); - 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; - } -}; + // Adds congruence x = a (mod m) + void add(ll a, ll m){ + ll s, t, d = extendedEuclid(M, m, s, t); + if((a - sol) % d != 0) hasSol = false; + lll z = M/d * s; + M *= m/d; + sol = (z % M * (a-sol) % M + sol + M) % M; + } +}; \ No newline at end of file -- cgit v1.2.3