本文主要是介绍再说中国剩余定理、扩展欧几里德与同余方程组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
在上篇博客中已经说了用中国剩余定理求同余方程组,这次又有所收获,故再详谈之。
在开始说中国剩余定理之前,再谈谈欧几里德算法和扩展欧几里德算法:
首先,欧几里德算法就是用递归的方式算两个数的最大公约数,其依据就是定理: gcd(a,b)=gcd(b,a mod b) (a>b 且 a mod b不为0)
代码就很容易了:
int gcd(int a,int b)
{
if(b==0)return a;
else return gcd(b,a%b);
}
再次,就是扩展欧几里德算法,先看内容:
对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by。
它也是用递归的方式实现,为什么用递归的呢??这是由它的推导过程决定的:
求解 x,y的方法的理解
设 a>b。
1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;
2,ab<>0 时
设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-[a/b]*b)y2=ay2+bx2-[a/b]*by2;
也就是ax1+by1==ay2+b(x2-[a/b]*y2);
根据恒等定理得:x1=y2; y1=x2-[a/b]*y2;
这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.
因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束(return a)。
设 a>b。
1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;
2,ab<>0 时
设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-[a/b]*b)y2=ay2+bx2-[a/b]*by2;
也就是ax1+by1==ay2+b(x2-[a/b]*y2);
根据恒等定理得:x1=y2; y1=x2-[a/b]*y2;
这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.
因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束(return a)。
再看代码:
int Egcd(int a,int b,int& x,int& y)
{
int d,t;
if(!b)
{
x=1;y=0;return a;
}
else
{
Egcd(b,a%b,y,x);
y-=x*(a/b);
}
}
我们分别设这个4个参数为: a:①,b:②,x:③,y:④ (注意,x,y传入的是地址,因为结果要放在x,y里)
故方程的形式:①*③+②*④=k(常数),故要想求③,把①、②、③、④按顺序放入Egcd的函数的参数中即可,便可得③。
欧几里德就说完了,接下来就是要说中国剩余定理了。
中国剩余定理简单来说就是:a = ai(mod ni),求未知数a。
设 n=n1*n2...nk, 其中因子两两互质.有: a-----(a1,a2,...,ak), 其中ai = a mod ni, 则 a和(a1,a2,...,ak)关系是一一对应的.就是说可以由 a求出(a1,a2,...,ak), 也可以由(a1,a2,...,ak)求出a。
下面说说由(a1, a2, ..., ak)求a的方法:
定义 mi = n1*n2*...nk / ni; ci = mi*(mf mod ni);(在这里,很多地方写的没有那个*号,我在这加上,大家就很明了了) 其中 mi*mf mod ni = 1;
则 a = (a1*c1+a2*c2+...+ak*ck) (mod n) (注:由此等式可求a%n, 当n很大时)。
定义 mi = n1*n2*...nk / ni; ci = mi*(mf mod ni);(在这里,很多地方写的没有那个*号,我在这加上,大家就很明了了) 其中 mi*mf mod ni = 1;
则 a = (a1*c1+a2*c2+...+ak*ck) (mod n) (注:由此等式可求a%n, 当n很大时)。
由a = (a1*c1+a2*c2+...+ak*ck) (mod n)可知,a是由ai和ci对应相乘再相加等到的,其中在题中ai应为余数(已知),ni为除数(已知),而ci是需要算的,且ci = mi*(mf mod ni),还有 mi = n1*n2*...nk / ni(已知),所以只需且关键求出mf!!mf怎么求,别闹,上边扩展欧几里德讲了那么多,可不是白说的,来,看!
mf求法:如果理解了扩展欧几里得 ax+by=d, 就可以想到:
mi*mf mod ni = 1 => mi*mf+ni*y=1;
对于这个式子 mi*mf+ni*y=1应该很熟悉吧,没错,就是用Egcd来求mf!
①:mi,②:ni,③:mf,④:y,不是想要mf吗?!把它放到③吧!
接下来就很简单了吧,看代码:
<span style="white-space:pre"> </span>for(i=0;i<n;i++)
s*=a[i];
for(i=0;i<n;i++)
{
m=s/a[i];<span style="white-space:pre"> </span>//m表示mi
gcd(m,a[i],x,y);
x=(x%a[i]+a[i])%a[i];
sum=(sum+m*b[i]*x%s)%s;<span style="white-space:pre"> </span>//在这里换做了吧b[i]表示余数了
}
好了,说完了,下面就是该题的全代码:
#include <stdio.h>
#include <string.h>
#include <math.h>
typedef __int64 int64; //这里要用64位
int64 a[11],b[11];
int64 gcd(int64 a,int64 b,int64& x,int64& y)
{
int64 d,t;
if(!b)
{
x=1;y=0;return a;
}
else
{
gcd(b,a%b,y,x);
y-=x*(a/b);
}
}
int main()
{
int64 sum,m,s,x,y;
int n,i;
while(scanf("%d",&n)!=EOF)
{
sum=0;s=1;
for(i=0;i<n;i++)
scanf("%I64d %I64d",&a[i],&b[i]);
for(i=0;i<n;i++)
s*=a[i];
for(i=0;i<n;i++)
{
m=s/a[i];
gcd(m,a[i],x,y);
x=(x%a[i]+a[i])%a[i];
sum=(sum+m*b[i]*x%s)%s;
}
printf("%I64d\n",sum); //既然要用64位,那输入输出也要用%I64d,否则用%d提交也会WA的。。。。
}
return 0;
}
这里把代码中的int 改成了int64,主要是为了保证一些比较大的数能够过。
这篇关于再说中国剩余定理、扩展欧几里德与同余方程组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!