summaryrefslogtreecommitdiff
path: root/math/chineseRemainder.cpp
diff options
context:
space:
mode:
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;
+ }
+};