This documentation is automatically generated by competitive-verifier/competitive-verifier
要素数 $n$ の配列 $B, M$ について,$x \equiv B_i \pmod{M_i}$ を満たす $x \equiv b \pmod m$ を求める.
crt(B, M)
:配列 B
, M
を引数にとり,pair(b, m)
を返す.条件を満たす $x$ が存在しない場合は pair(0, 0)
を返す.$\operatorname{lcm}(M_1,\ M_2,\ …\ ,\ M_n) \leq$ LLONG_MAX
である必要がある.crt(B, M)
:$O(n \log M_{\max})$$x$ について,合同式 $x \equiv b \pmod m$ と表現できる最小の $m$ は $\operatorname{lcm}(M_1,\ M_2,\ …\ ,\ M_n)$ である.
#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
#include "../math/extgcd.cpp"
pair<long long, long long> crt(const vector<long long> &B, const vector<long long> &M) {
long long r = 0, m = 1, p, q, d;
for(int i = 0; i < B.size(); i++) {
d = extgcd(m, M[i], B[i] - r, p, q);
if(d == -1) return make_pair(0LL, 0LL);
r += p % (M[i] / d) * m; // r = r + m * p
m *= M[i] / d; // m = lcm(m, M[i])
r %= m; // r = r % lcm(m, M[i])
if(r < 0) r += m;
}
return make_pair(r, m);
}
#line 2 "math/chinese_remainder_theorem.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
#line 2 "math/extgcd.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
long long extgcd(long long a, long long b, long long &x, long long &y) {
long long x_ = abs(a), xd = 1, xdd = 0, y_ = abs(b), yd = 0, ydd = 1, div;
while(true) {
if(!y_) {
x = xd;
y = xdd;
return x_;
}
div = x_ / y_;
x_ -= div * y_;
xd -= div * yd;
xdd -= div * ydd;
if(!x_) {
x = yd;
y = ydd;
return y_;
}
div = y_ / x_;
y_ -= div * x_;
yd -= div * xd;
ydd -= div * xdd;
}
if(a < 0) x = -x;
if(b < 0) y = -y;
}
long long extgcd(long long a, long long b, long long c, long long &x, long long &y) {
long long d = extgcd(a, b, x, y);
if(c % d) return -1;
if(a != 0) {
x *= c % a / d;
y *= c % a / d;
x += c / a;
}
else {
y *= c / d;
}
return d;
}
#line 10 "math/chinese_remainder_theorem.cpp"
pair<long long, long long> crt(const vector<long long> &B, const vector<long long> &M) {
long long r = 0, m = 1, p, q, d;
for(int i = 0; i < B.size(); i++) {
d = extgcd(m, M[i], B[i] - r, p, q);
if(d == -1) return make_pair(0LL, 0LL);
r += p % (M[i] / d) * m; // r = r + m * p
m *= M[i] / d; // m = lcm(m, M[i])
r %= m; // r = r % lcm(m, M[i])
if(r < 0) r += m;
}
return make_pair(r, m);
}