summaryrefslogtreecommitdiff
path: root/math/chineseRemainder.cpp
diff options
context:
space:
mode:
authorGloria Mundi <gloria@gloria-mundi.eu>2024-04-01 19:59:01 +0200
committerGloria Mundi <gloria@gloria-mundi.eu>2024-04-01 19:59:01 +0200
commit33343f96d94f2d7f12567b1c227e4e2399c8bd1b (patch)
tree16b5ef80ee4605ce88410911fbb6beb6dfc1d7b2 /math/chineseRemainder.cpp
parent4fc39dcd54243609febc1ce4c8a1470b3d31fd47 (diff)
parent98aa28427350e72cb9abe4071c0c6b6870b7e6cc (diff)
merge mzuenni changes
Diffstat (limited to 'math/chineseRemainder.cpp')
-rw-r--r--math/chineseRemainder.cpp26
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;
+ }
+};