diff options
| author | Gloria Mundi <gloria@gloria-mundi.eu> | 2024-04-01 19:59:01 +0200 |
|---|---|---|
| committer | Gloria Mundi <gloria@gloria-mundi.eu> | 2024-04-01 19:59:01 +0200 |
| commit | 33343f96d94f2d7f12567b1c227e4e2399c8bd1b (patch) | |
| tree | 16b5ef80ee4605ce88410911fbb6beb6dfc1d7b2 /math/chineseRemainder.cpp | |
| parent | 4fc39dcd54243609febc1ce4c8a1470b3d31fd47 (diff) | |
| parent | 98aa28427350e72cb9abe4071c0c6b6870b7e6cc (diff) | |
merge mzuenni changes
Diffstat (limited to 'math/chineseRemainder.cpp')
| -rw-r--r-- | math/chineseRemainder.cpp | 26 |
1 files changed, 13 insertions, 13 deletions
diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index a1aa480..ccbc5dc 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,14 +1,14 @@ -struct CRT{ - using lll = __int128_t; - lll M = 1, sol = 0; // Solution unique modulo M - bool hasSol = true; +struct CRT { + using lll = __int128; + lll M = 1, sol = 0; // Solution unique modulo M + bool hasSol = true; - // 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 + // Adds congruence x = a (mod m) + void add(ll a, ll m) { + auto [d, s, t] = extendedEuclid(M, m); + if((a - sol) % d != 0) hasSol = false; + lll z = M/d * s; + M *= m/d; + sol = (z % M * (a-sol) % M + sol + M) % M; + } +}; |
