数论-中国剩余定理

含义

中国剩余定理:

设$m_1,m_2,…,m_k$是$k$个两两互质的正整数,$M_i=\frac M{m_i}(i=1,2,3,…,k),b_1,b_2,…,b_k$为任意整数,则同余式组
$$x\equiv b_1\pmod {m_1},…,x\equiv b_k\pmod{m_k}$$
有唯一解$x\equiv M_1^M_1b_1+…+M_k^M_ib_k\pmod M$,其中满足$M_i^*M_i\equiv 1\pmod m_i任意整数(i=1,2,…,k)$。

思维训练

问题描述

今有物不知其数,三三数之余二;五五数之余三;七七数之余二。问物几何?

问题分析

答案是23。
我们要先解三个特殊的同余方程组。
\begin{cases}
x\equiv 1\pmod 3\[2ex]
x\equiv 0\pmod 5\[2ex]
x\equiv 0\pmod 7\[2ex]
\end{cases}
\begin{cases}
x\equiv 0\pmod 3\[2ex]
x\equiv 1\pmod 5\[2ex]
x\equiv 0\pmod 7\[2ex]
\end{cases}
\begin{cases}
x\equiv 0\pmod 3\[2ex]
x\equiv 0\pmod 5\[2ex]
x\equiv 1\pmod 7\[2ex]
\end{cases}
$$
\begin{pmatrix}
1\
0\
0\
\end{pmatrix}=70
$$
$$
\begin{pmatrix}
0\
1\
0\
\end{pmatrix}=21
$$
$$
\begin{pmatrix}
0\
0\
1\
\end{pmatrix}=15
$$
所以
$$
\begin{pmatrix}
2\
3\
2\
\end{pmatrix}
=2
\begin{pmatrix}
1\
0\
0\
\end{pmatrix}
+3
\begin{pmatrix}
0\
1\
0\
\end{pmatrix}
+2
\begin{pmatrix}
0\
0\
1\
\end{pmatrix}
=2\times 70+3\times 21+2\times 15\equiv 23\pmod {105}
$$

通过这个例子,大家都应该知道中国剩余定理怎么用了吧。

代码

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
int extended_gcd(int a,int b,int &x,int &y)
{
int ret,tmp;
if(!b)
{
x=1;
y=0;
return a;
}
ret=extended_gcd(b,a%b,x,y);
tmp=x;
x=y;
y=tmp-a/b*y;
return ret;
}
int China(int W[],int B[],int k)
{
int x,y,a=0,m,n=1;
for(int i=0;i<k;i++)
n*=W[i];
for(int i=0;i<k;i++)
{
m=n/W[i];
extended_gcd(W[i],m,x,y);
a=(a+y*m*B[i])%n;
}
return a>0 ? a:a+n;
}

曹冲养猪

曹冲养猪题目地址

分析

裸的中国剩余定理!

代码

这道题目坑的地方就是炸int。

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
#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
long long num=0;
char c=' ';
bool flag=true;
for(;c>'9'||c<'0';c=getchar())
if(c=='-')
flag=false;
for(;c>='0'&&c<='9';num=num*10+c-48,c=getchar());
return flag ? num : -num;
}
#define maxn 12
long long a[maxn],b[maxn];
long long n;
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 gcd=exgcd(b,a%b,x,y);
long long t=x;
x=y;
y=t-a/b*y;
return gcd;
}
long long China()
{
long long x,y,ans=0,m,pai=1;
for(int i=1;i<=n;i++)
pai*=a[i];
for(int i=1;i<=n;i++)
{
m=pai/a[i];
exgcd(a[i],m,x,y);
ans=(ans+y*m*b[i])%pai;
}
return ans>0 ? ans : ans+pai;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
b[i]=read();
}
printf("%lld\n",China());
return 0;
}

文章目录
  1. 1. 含义
  2. 2. 思维训练
    1. 2.1. 问题描述
    2. 2.2. 问题分析
  3. 3. 代码
  4. 4. 曹冲养猪
    1. 4.1. 分析
    2. 4.2. 代码