中国剩余定理
2022-03-09 22:49:00 # 数论

中国剩余定理

介绍

中国剩余定理(Chinese remainder theorem, CRT)

img

cpp

P1495 【模板】中国剩余定理(CRT)/曹冲养猪

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

long long exgcd(long long a, long long b, long long &x, long long &y){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	long long res = exgcd(b, a%b, x, y);
	long long t = x;
	x = y;
	y = t - a/b*y;
	return res;
}

// x = a (mod b)
// A[0...size-1], B[0...size-1]
long long CRT(long long A[], long long B[], long long size){
	long long mulSumB = 1, res = 0;
	for(int i=0;i<size;i++) mulSumB *= B[i];
	for(int i=0;i<size;i++){
		long long t = mulSumB/B[i];
		long long x, y;
		exgcd(t, B[i], x, y); // x 为 t 在模 B[i] 下的逆元
		res = ( res + A[i]*t*x%mulSumB ) % mulSumB;
	}
	return (res % mulSumB + mulSumB) % mulSumB;
}

void solve(){
	long long n;
	long long A[10], B[10];
	cin >> n;
	for(int i=0;i<n;i++) cin >> A[i] >> B[i];
	cout << CRT(B, A, n) << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	int ce = 1;
//	cin >> ce;
	while(ce--) solve();
	
	return 0;
}

扩展中国剩余定理

介绍

与 中国剩余定理 没啥关系

img

cpp

P4777 【模板】扩展中国剩余定理（EXCRT）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b){
	return b == 0 ? a : gcd(b, a%b);
}

long long slowMul(long long a, long long b, long long mod){
	long long ans = 0;
	for(;b;b>>=1){
		if(b&1) ans = (ans + a) % mod;
		a = (a + a) % mod;
	}
	return ans;
}

long long exgcd(long long a, long long b, long long &x, long long &y){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	long long res = exgcd(b, a%b, x, y);
	long long t = x;
	x = y;
	y = t - a/b*y;
	return res;
}

// x = a (mod b)
// A[0...size-1], B[0...size-1]
long long EXCRT(long long A[], long long B[], long long size){
	long long res = A[0], LCM = B[0];
	for(int i=1;i<size;i++){
		long long c, x, y;
		c = ( (A[i] - res)%B[i] + B[i] ) % B[i];
		long long g = exgcd(LCM, B[i], x, y);
//		x = x * c/g % B[i];
		x = slowMul(x, c/g, B[i]);
		res += x * LCM;
		LCM *= B[i] / g;
		res = (res + LCM) % LCM;
	}
	return res;
}

void solve(){
	int n; 
	long long A[100000], B[100000];
	cin >> n;
	for(int i=0;i<n;i++) cin >> B[i] >> A[i];
	long long ans = EXCRT(A, B, n);
	cout << ans << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	int ce = 1;
//	cin >> ce;
	while(ce--) solve();
	
	return 0;
}
Prev
2022-03-09 22:49:00 # 数论
Next