extended_gcd.hpp¶
#include "noya/extended_gcd.hpp"
#ifndef NOYA_EXTENDED_GCD_HPP
#define NOYA_EXTENDED_GCD_HPP 1
#include <algorithm>
#include <cassert>
#include <vector>
namespace noya {
/// @brief Compute gcd(a, b) and coefficients x, y such that a*x + b*y = gcd.
template <typename T> T extgcd(T a, T b, T &x, T &y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
T p = b / a;
T g = extgcd(b - p * a, a, y, x);
x -= p * y;
return g;
}
/// @brief Solve a*x + b*y = c for integers x, y; returns false if no solution.
template <typename T> bool diophantine(T a, T b, T c, T &x, T &y, T &g) {
if (a == 0 && b == 0) {
if (c == 0) {
x = y = g = 0;
return true;
}
return false;
}
if (a == 0) {
if (c % b == 0) {
x = 0;
y = c / b;
g = abs(b);
return true;
}
return false;
}
if (b == 0) {
if (c % a == 0) {
x = c / a;
y = 0;
g = abs(a);
return true;
}
return false;
}
g = extgcd(a, b, x, y);
if (c % g != 0) {
return false;
}
T dx = c / a;
c -= dx * a;
T dy = c / b;
c -= dy * b;
x = dx + (T)((__int128)x * (c / g) % b);
y = dy + (T)((__int128)y * (c / g) % a);
g = abs(g);
return true;
}
/// @brief Chinese Remainder Theorem for two congruences; returns false if no solution.
inline bool crt(long long k1, long long m1, long long k2, long long m2,
long long &k, long long &m) {
k1 %= m1;
if (k1 < 0)
k1 += m1;
k2 %= m2;
if (k2 < 0)
k2 += m2;
long long x, y, g;
if (!diophantine(m1, -m2, k2 - k1, x, y, g)) {
return false;
}
long long dx = m2 / g;
long long delta = x / dx - (x % dx < 0);
k = m1 * (x - dx * delta) + k1;
m = m1 / g * m2;
assert(0 <= k && k < m);
return true;
}
/// @brief Garner's algorithm for CRT with multiple moduli; stores result in res.
template <typename T>
void crt_garner(const std::vector<int> &p, const std::vector<int> &a, T &res) {
assert(p.size() == a.size());
auto inverse = [&](int q, int m) {
q %= m;
if (q < 0)
q += m;
int b = m, u = 0, v = 1;
while (q) {
int t = b / q;
b -= t * q;
std::swap(q, b);
u -= t * v;
std::swap(u, v);
}
assert(b == 1);
if (u < 0)
u += m;
return u;
};
std::vector<int> x(p.size());
for (int i = 0; i < (int)p.size(); i++) {
assert(0 <= a[i] && a[i] < p[i]);
x[i] = a[i];
for (int j = 0; j < i; j++) {
x[i] = (int)((long long)(x[i] - x[j]) * inverse(p[j], p[i]) % p[i]);
if (x[i] < 0)
x[i] += p[i];
}
}
res = 0;
for (int i = (int)p.size() - 1; i >= 0; i--) {
res = res * p[i] + x[i];
}
}
} // namespace noya
#endif // NOYA_EXTENDED_GCD_HPP
#include <algorithm>
#include <cassert>
#include <vector>
namespace noya {
/// @brief Compute gcd(a, b) and coefficients x, y such that a*x + b*y = gcd.
template <typename T> T extgcd(T a, T b, T &x, T &y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
T p = b / a;
T g = extgcd(b - p * a, a, y, x);
x -= p * y;
return g;
}
/// @brief Solve a*x + b*y = c for integers x, y; returns false if no solution.
template <typename T> bool diophantine(T a, T b, T c, T &x, T &y, T &g) {
if (a == 0 && b == 0) {
if (c == 0) {
x = y = g = 0;
return true;
}
return false;
}
if (a == 0) {
if (c % b == 0) {
x = 0;
y = c / b;
g = abs(b);
return true;
}
return false;
}
if (b == 0) {
if (c % a == 0) {
x = c / a;
y = 0;
g = abs(a);
return true;
}
return false;
}
g = extgcd(a, b, x, y);
if (c % g != 0) {
return false;
}
T dx = c / a;
c -= dx * a;
T dy = c / b;
c -= dy * b;
x = dx + (T)((__int128)x * (c / g) % b);
y = dy + (T)((__int128)y * (c / g) % a);
g = abs(g);
return true;
}
/// @brief Chinese Remainder Theorem for two congruences; returns false if no solution.
inline bool crt(long long k1, long long m1, long long k2, long long m2,
long long &k, long long &m) {
k1 %= m1;
if (k1 < 0)
k1 += m1;
k2 %= m2;
if (k2 < 0)
k2 += m2;
long long x, y, g;
if (!diophantine(m1, -m2, k2 - k1, x, y, g)) {
return false;
}
long long dx = m2 / g;
long long delta = x / dx - (x % dx < 0);
k = m1 * (x - dx * delta) + k1;
m = m1 / g * m2;
assert(0 <= k && k < m);
return true;
}
/// @brief Garner's algorithm for CRT with multiple moduli; stores result in res.
template <typename T>
void crt_garner(const std::vector<int> &p, const std::vector<int> &a, T &res) {
assert(p.size() == a.size());
auto inverse = [&](int q, int m) {
q %= m;
if (q < 0)
q += m;
int b = m, u = 0, v = 1;
while (q) {
int t = b / q;
b -= t * q;
std::swap(q, b);
u -= t * v;
std::swap(u, v);
}
assert(b == 1);
if (u < 0)
u += m;
return u;
};
std::vector<int> x(p.size());
for (int i = 0; i < (int)p.size(); i++) {
assert(0 <= a[i] && a[i] < p[i]);
x[i] = a[i];
for (int j = 0; j < i; j++) {
x[i] = (int)((long long)(x[i] - x[j]) * inverse(p[j], p[i]) % p[i]);
if (x[i] < 0)
x[i] += p[i];
}
}
res = 0;
for (int i = (int)p.size() - 1; i >= 0; i--) {
res = res * p[i] + x[i];
}
}
} // namespace noya