Skip to content

Instantly share code, notes, and snippets.

@miguelAlessandro
Created June 11, 2019 18:05
Show Gist options
  • Save miguelAlessandro/0200e87aa7bda06e9fe2905138457b5b to your computer and use it in GitHub Desktop.
Save miguelAlessandro/0200e87aa7bda06e9fe2905138457b5b to your computer and use it in GitHub Desktop.
number theory algorithms
//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