Created
June 11, 2019 18:05
-
-
Save miguelAlessandro/0200e87aa7bda06e9fe2905138457b5b to your computer and use it in GitHub Desktop.
number theory algorithms
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//gcd | |
int gcd(int a, int b) { | |
return b!=0 : gcd(b, a%b), a; | |
} | |
//extended gcd | |
int exgcd(int a, int b, int& x, int& y) { | |
if (b == 0) { | |
x = 1; y = 0; | |
return a; | |
} | |
int x1, y1; | |
int g = gcd(b, a%b, x1, y1); | |
x = y1; | |
y = x1 - (a/b) * y1; | |
return g; | |
} | |
//inverse a (mod b) | |
int inv(int a, int b) { | |
int x, y; | |
int g = exgcd(a, b, x, y); | |
return g==1 ? (x%b + b) % b : -1; | |
} | |
// a + b (mod m) | |
int add(int a, int b, int m) { | |
return (a + b) % m; | |
} | |
//a * b (mod m) | |
int mul(long long a, long long b, int m) { | |
return a * b % m; | |
} | |
//a * b (mod m) if m is long long | |
long long mul(long long a, long long b, long long m) { | |
long long r = 0; | |
while (b > 0) { | |
if (b&1) r = add(r, a); | |
a = add(a, a); | |
b >>= 1; | |
} | |
return b; | |
} | |
//a^b (mod m) | |
int ex(int a, int b, int m) { | |
int r = 1; | |
while (b > 0) { | |
if (b&1) r = mul(r, a); | |
a = mul(a, a); | |
b >>= 1; | |
} | |
return r; | |
} | |
//chinese remainder theorem | |
/** | |
* solve: | |
* ai = x (mod bi) | |
*/ | |
int crt(vector<int> a, vector<int> b) { | |
int A = a[0], B = b[0]; | |
int n = a.size(); | |
for (int i = 1; i < n; ++i) { | |
int x, y; | |
int g = exgcd(B, b[i], x, y); | |
A -= (a[i] - A) / g * x * B; | |
B *= b[i] / g; | |
A = (A % B + B) % B; | |
} | |
return A; | |
} | |
//find generator | |
[emaxx-eng](https://cp-algorithms.com/algebra/primitive-root.html) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment