中国剩余定理

Nannan Lv5
  2023-09-30 19:42 2023-09-30 19:42 Created   2024-09-30 19:56:55 2024-09-30 19:56:55 Updated      

Chinese Remainder Theorem


中国剩余定理CRT

1.定义

Th.
给出一元线性同余线性方程组


…

定理指出假设素数两两互素,对任意的整数
上述方程有解，并且可以通过如下步骤构造通解：
1>计算(即,Mi是除之外的其他整数的乘积)
2>计算为模的逆,对于计算满足的
3>上述方程的通解为:

在模的意义下,方程组只有一个解

2.写法

1.互质的写法(useless)










$x = 270+321+415 = 263 2(1,0,0) 3*(0,1,0) 4*(0,0,1) (2,0,0) (0,0,4) (2,3,4)x105 = 53$

总结:
对于个

我们先去解个

其他

$xi \bmod (m1m2..mi-1mi+1…mn) = 0即xi \bmod (\frac{M}{mi}) = 0 xi \bmod mi = 1设xi = (\frac{M}{mi})*t则有(\frac{M}{mi})*t \bmod mi = 1$

比如上述例子






即$Miti ≡ 1(\bmod mi)xi = Miti x = Σaixi$

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5 + 7;
int n, a[N], m[N];
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0){
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll z = x;x = y;y = z - (a / b) * x;
    return d;
}
int main()
{
   int t;
   cin>>t;
   while(t--)
   {
	   	ll M = 1;
	    scanf("%d", &n);
	    for(int i = 1; i <= n; ++ i) 
	    {
	        scanf("%d%d", &a[i], &m[i]);
	        M *= m[i];
	    }
	    ll res = 0;
	    for(int i = 1; i <= n; ++ i) 
	    {
	        ll Mi = M / m[i];
	        ll ti, y;
	        //exgcd求逆元：解同余方程：ax + my = 1;(ax ≡ 1 mod m)
	        ll d = exgcd(Mi, m[i], ti, y);
	        ti = (ti % m[i] + m[i]) % m[i];
	        res += a[i] * ti * Mi;
	    }
	    printf("%lld\n", (res % M + M) % M);//可能为负数，所以需要处理一下
   }
    return 0;
}

2.对于不互质的情况(增量法)

一开始有两个方程
设
那么有

要有解要被整除

$t ≡ (c-a)’(b’^{-1})(mod \dfrac{d}{(b,d)})设t0 = (c-a)’(b’^{-1})转化为线性同余方程，然后解出t ≡ t0(\bmod \dfrac{d}{(d,b)}) t ≡ t0(\bmod \dfrac{d}{g})再代回去x ≡ bt0+a(\bmod \dfrac{bd}{g})$

得出
然后下一条方程,
可以解决模数不互质的情况
即在不互质的情况下，要么无解，要么在的意义下有唯一解

.
①
②
③

先连立前两个方程④
在联立③④得

①
②
③

代入②得：



再将带回去④
在联立③④：
令代入③得:



再将带回去

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
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x = 1,y = 0;
		return a;
	}
	ll d = exgcd(b,a%b,y,x);
	y -= (a/b)*x;
	return d;
}

void merge(ll &a,ll&b,ll c,ll d)
{
   
    /*
    	x = a+Xb
    	x = c+Yd
    	a+Xb = c+Yd
    	Xb+(-Y)d = c-a
    	这里用exgcd求X0
    	X的通解是X=X0*(c-a)/g+d/g*n(任意整数)
    	最小值是t0 = X0*(c-a)/g mod d/g
    	把X = t0,代入x=a+Xb,得原式第一个特解x'
    	合并后新的x=a+Xb
    	其中a = x',b = b*d/gcd(b,d)
    */
	if(a==-1&&b==-1)return;
	//bt = c-a(mod d)
	ll x,y;
	ll g = exgcd(b,d,x,y);
	//x = b^(-1)
	if((c-a)%g!=0)
	{
		a = b = -1;
		return;
	}
	d/=g;//d'
	ll t0 = ((c-a)/g)%d*x%d;
	if(t0<0)t0+=d;
	a = b*t0+a;
	b = b*d;
}

void solve()
{
	cin>>n;
	ll a = 0,b = 1;//x ≡ a(mod b),x = a+kb
	for(int i = 1;i<=n;i++)
	{
		int c,d;
		cin>>c>>d;
		merge(a,b,c,d);
	}
	cout<<a<<endl;
}


int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

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
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x = 1,y = 0;
		return a;
	}
	ll d = exgcd(b,a%b,y,x);
	y -= (a/b)*x;
	return d;
}

ll mul(ll a,ll b,ll m)
{
	ll ans = 0;
	while(b)
	{
		if(b&1)
		{
			ans = (ans+a)%m;
		}
		(a<<=1)%=m;
		b>>=1;
	}
	return ans;
}

void merge(ll &a,ll &b,ll c,ll d)
{
	if(a==-1&&b==-1)return;
	ll x, y;
	ll g = exgcd(b,d,x,y);
	if((c-a)%g)
	{
		a = b = -1;
		return;
	}
	ll t0 = ((c-a)/g)%(d/g)*x%(d/g);
	if(t0<0)t0+=(d/g);
	a = a+t0*b;
	b = b*d/g;
}


int main()
{
	int n;
	cin>>n;
	ll a = 0,b = 1,c,d;
	for(int i = 1;i<=n;i++)
	{
		long long _c,_d;
		cin>>_d>>_c;
		d = _d,c = _c;
		merge(a,b,c,d);
	}
	cout<<(long long)a<<endl;
	return 0;
}

例题：中国剩余定理2

一共组数据，每组数据，给定个方程，
。判断方程是不是有解。

x mod 合数 = a ==>等价于模数是素数幂的方程，再去判断有没有解，我们还是用中国剩余定理
且

且

模数按照素数的幂次分类，比如(*)式看成一类，我们只需要看其中指数最高的那个方程，但我们还是要判前面满不满足的，比如我们既有一个方程又有个方程这样也是不行的

转化：
对合数取模
|
CRT
↓
对素数幂取模

即：


|
CRT
↓
然后对于每个素数幂的我们都check一下是否都是满足的
|
CRT
↓

若满足，则有解

总结：对合数取模 <=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
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool solve()
{
	int n;
	cin>>n;
	map<int,vector<pair<int,int>>>eqns;

	for(int i = 1;i<=n;i++)
	{
		int a,m;
		cin>>a>>m;
		for(int j = 2;j*j<=m;j++)//分解为素数幂
		{
			if(m%j==0)
			{
				int p = j,pe = 1;
				while(m%j==0)
					m/=j,pe*=j;
				eqns[p].push_back({pe,a%pe});	
			}
		}
		if(m>1)eqns[m].push_back({m,a%m});
	}
	for(auto eq:eqns)
	{
		auto eqn = eq.second;
		int v = max_element(eqn.begin(),eqn.end())->second;//最后的余数由指数最大的所决定
		for(auto p:eqn)
		{
			if(v%p.first!=p.second)return false;
		}
	}
	return true;
}


int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		if(solve())
			cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}
  • Title: 中国剩余定理
  • Author: Nannan
  • Created at : 2023-09-30 19:42:00
  • Updated at : 2024-09-30 19:56:55
  • Link: https://redefine.ohevan.com/2023/09/30/三、Chinese Remainder Theorem/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
中国剩余定理
  1. Chinese Remainder Theorem
    1. 1.定义
    2. 2.写法
      1. 1.互质的写法(useless)
      2. 2.对于不互质的情况(增量法)
        1. P4777 【模板】扩展中国剩余定理（EXCRT）
        2. 例题：中国剩余定理2