中国剩余定理
2019-08-16 07:53:27来源:博客园 阅读 ()
中国剩余定理
导入
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
上述的一段诗句出自 《孙子算经》 (该书中首次提到了同余方程组问题,以及此问题的解法,因此有些地方也会将中国剩余定理称为孙子定理
)。 言归正转 ,上述诗句翻译成现代数学的语言即为:
有一个正整数n,满足n%3==2,n%5==3,n%7==2,求这个正整数n。
毫无疑问,满足条件的最小正整数n有无穷多个,我们需要解决的问题是n的最小值为多少。那么如何解决这个问题呢?我们先来了解了解古人的解法:
三人同行七十稀,五树梅花廿一枝,七子团圆月正半,除百零五便得知。
仅仅二十八个字,古人便将上述问题的解题过程讲述得即为具体,可能,你却听得一头雾水。别急,我先翻译一下:
23≡2*70+3*21+2*15(mod 105)
//≡为恒等号
//注意70,21,15这三个数,以下有用
答曰:二十三。
当然,我们可以轻松地验证出23的确为符合要求的最小正整数解, 但是 ,我们所要了解的是如何快速地求出最小正整数解n,这就需要我们熟练地掌握 中国剩余定理 。
同余
中国剩余定理是用以解决同余方程组问题,那么我们要想学懂中国剩余定理,那么同余方程的概念
及同余方程的一些性质
便好比先行管。
同余:如果有两个数a与b,且有一除数c,使得a mod c≡b mod c
,那么我们就说a和b关于c同余
。记作a≡b(mod c)
。
对于两个数a与b与除数c,有一下一些性质:
性质一:若a1≡b1(mod c),a2≡b2(mod c),则a1+a2≡b1+b2(mod c)
性质二:若a1≡b1(mod c),则a1*d≡b1*d(mod c)
古人的思维
既然大家此时此刻都已经了解同余方程,那么我们便将原问题转化为以下的同余方程组:
n≡2(mod 3)
n≡3(mod 5)
n≡2(mod 7)
设x为上述同余方程组的最小正整数解,则x+105*k(k为整数)
虽然不是最小正整数解,但也是上述同余方程组的一组可行解(性质一,105*k%c比为0)
接着解下列三个特殊同余方程组的解
同余方程组一:
x≡1(mod 3)
x≡0(mod 5)
x≡0(mod 7)
同余方程组二:
x≡0(mod 3)
x≡1(mod 5)
x≡0(mod 7)
同余方程组三:
x≡0(mod 3)
x≡0(mod 5)
x≡1(mod 7)
以同余方程组一为例,由于x≡0(mod 5)且x≡0(mod 7)
,故x为35的倍数,则设x=35y
,则x≡1(mod 3)
就转化成了35y≡1(mod 3)
,即有35y+3yy==1,扩展欧几里德定理可以求得y=2,于是x=35*2=70(mod 105)。同理,同余方程组二的解为x=21;同余方程组三的解为x=15。
同样考虑同余方程组一,由性质二得出x*2=1*2(mod 105)
,故满足n≡2(mod 3)
的解为x1=35。同理,x2=63;x3=30。
所以:最小正整数解n=(x1+x2+x3)%105=(35+63+30)%105=23。
中国剩余定理
接下来我们正式谈谈中国剩余定理。先讲讲中国剩余定理的一般形式:
已知b1,b2,b3,…,bn为互质的正整数,且有:
n≡a1(mod b1)
n≡a2(mod b2)
n≡a3(mod b3)
……
n≡an(mod bn)
求最小正整数解n。
转化
n1≡1(mod b1)
n2≡0(mod b2)
n3≡0(mod b3)
……
nn≡0(mod bn)
n1≡0(mod b1)
n2≡1(mod b2)
n3≡0(mod b3)
……
nn≡0(mod bn)
……
n1≡0(mod b1)
n2≡0(mod b2)
n3≡0(mod b3)
……
nn≡1(mod bn)
重点:考虑第一组方程组,设m=b1*b2*b3*…*bn
,m1=m/b1
,n1=m1*x
,则方程等价于m1*x≡1(mod b1)
→m1*x+b1*y≡1
,扩欧得出x,则n1=m1*x
,所以方程组的解为n=a1*n1+a2*n2+…+an*nn(mod m)
模板
模板题:1402 猪的安家
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=11;
ll a[N],b[N];
void Gcd(ll n1,ll n2,ll &x,ll &y)
{
if (n1%n2==0) {x=0,y=1;return;}
Gcd(n2,n1%n2,x,y);
ll t;
t=x,x=y,y=t-(n1/n2)*y;
}
ll Calc(int n)
{
ll m=1,Res=0,mi,x,y; int i;
for (i=1;i<=n;++i) m*=a[i];
for (i=1;i<=n;++i)
{
mi=m/a[i];
Gcd(mi,a[i],x,y);
x=(x%a[i]+a[i])%a[i],
Res=(Res+mi*b[i]*x%m)%m;
}
return (Res+m)%m;
}
int main()
{
int n,i;
while (~scanf("%d",&n))
{
for (i=1;i<=n;++i) cin>>a[i]>>b[i];
cout<<Calc(n)<<endl;
}
return 0;
}
原文链接:https://www.cnblogs.com/hihocoder/p/10848581.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:长乐培训Day3
下一篇:c++ 学习笔记(一)
- 最小割最大流定理&残量网络的性质 2019-12-17
- Lucas定理模板 2019-08-16
- 费马小定理入门 2019-08-16
- 中国象棋 2019-08-16
- 『ACM C++』HDU杭电OJ | 1415 - Jugs (灌水定理引申) 2019-02-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash