【数学】【NOIp2012】同余方程题解以及关于扩展欧几里得与同余方程

什么是GCD？

GCD是最大公约数的简称（当然理解为我们伟大的党也未尝不可）。在开头，我们先下几个定义：
①a|b表示a能整除b（a是b的约数）
②a mod b表示a-[a/b]b（[a/b]在Pascal中相当于a div b）
③gcd(a,b)表示a和b的最大公约数
④a和b的线性组合表示ax+by（x,y为整数）。我们有：若d|a且d|b，则d|ax+by（这很重要！）

由这条定理易推知：若d|a且d|b，则d|gcd(a,b)

扩展欧几里得是对于一对整数a,b总可以找到一组解x,y使ax+by=gcd(a,b)

例如a=6,b=15时,gcd(a,b)=3;一组可行的解是x=3,y=-1,当然还有其他解如x=-2,y=1.

给出实现程序

1 int exGcd(int a,int b,int &d,int &x,int &y)//d表示gcd(a,b)
2 {
3     if(!b){d=a;x=1;y=0;}
4     else {exGcd(b,a%b,d,y,x);y-=x*(a/b);}
5 }

我们说过，gcd(a,b)可以表示为a和b的最小的正线性组合。现在我们就要求这个最小的正线性组合ax+by中的x和y。

从最简单的情况开始。当b=0时，我们取x=1,y=0。当b≠0时呢？
假设gcd(a,b)=d，则gcd(b,a mod b)=d。若我们已经求出了gcd(b,a mod b)的线性组合表示bx'+(a mod b)y'，则
gcd(a,b)=d
=bx'+(a mod b)y'
=bx'+(a-[a/b]b)y'

=ay'+b(x'-[a/b]y')=d=ax+by

那么，x=y'，y=x'-[a/b]y'。这样就可以在Euclid的递归过程中求出x和y。

所以在上述代码的第4行中：

　　　　x=y';(即x与y交换)

　　　　(交换前)y=x'-(a/b)*y';

　　　　(交换后)y=y'-(a/b)*x';

　　所以递归时

　　　　exGcd(b,a%b,d,y,x);交换了x,y
　　　　y-=x*(a/b);//更新了y

求出了一组解肯定远远不够,如何求出其他解呢?一个公式就可以解决,对于方程的一个解(x₀,y₀)它的任意整数解可以表示为

　　(x₀+ k*(b/d),y₀- k*(a/d))

推导过程为:
　　设(x1,y1)为方程的一组已知解,(x2,y2)为一组未知解,代入方程后得:

　　a*x1+b*y1=d;

　　a*x2+b*y2=d;

　　a*x1+b*y1=a*x2+b*y2

　　移项得:

　　a*(x1-x2)=b*(y1-y2)

　　两边同时除以d(令a'=a/d,b'=b/d)

　　a'*(x1-x2)=b'*(y1-y2)

　　a' 与 b' 一定互质

　　(x1-x2)一定可以被b整除

　　设x1-x2=k*b'

　　a'*k*b'=b'*(y1-y2)

　　k*a'=y1-y2

　　所以x2=x1-k*b'

　　　　y2=y1+k*a'

同余方程:aΞb(mod n)表示(a mod n)==(b mod n)即a-b可以被n整除(注意是整除);

所以可以设ax-b为n的正整数倍,所以又可以设ax-b为n的y倍;

得到ax-b==ny变形得ax-ny==b;

这下就可以用扩展欧几里得解决了!

相关的例题在Vijos P1781 同余方程,2012年提高组的题,如果知道了这个方程,那AC简直妥妥的!下面是AC代码

 1 /*
 2 ID: ringxu97
 3 LANG: C++
 4 TASK: NOIp2012-同余方程 
 5 SOLUTION: 扩展欧几里得 同余方程的解法 
 6 */
 7 #include<cstdio>
 8 #include<cstring>
 9 #include<iostream>
10 #include<cmath>
11 #include<cstdlib>
12 #include<algorithm>
13 using namespace std;
14 int exgcd(int a,int b,int &d,int &x,int &y)
15 {
16     if(!b){d=a;x=1;y=0;}
17     else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}
18 }
19 int main()
20 {
21     int a,b;
22     scanf("%d%d",&a,&b);
23     int g,x,y;
24     exgcd(a,b,g,x,y);
25     int ans=x;
26     while(ans<0)ans+=b/g;
27     printf("%d
",ans);
28     return 0;
29 }

View Code

【数学】【NOIp2012】同余方程 题解 以及 关于扩展欧几里得与同余方程

【数学】【NOIp2012】同余方程题解以及关于扩展欧几里得与同余方程