Chinese-Remainder-Theorem(中国剰余定理) (math/chinese_remainder_theorem.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-09 13:05:12+09:00

なにこれ

要素数 $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)$ である．

参考

• 中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita

Depends on

• extgcd(拡張ユークリッドの互除法) (math/extgcd.cpp)

Verified with

• test/yuki_0186.cpp

Code

#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);
}

Back to top page