这是一道扩展欧几里德的题,对于我这个才学算法半年的新手来说,理解它还是花了不少时间的。下面详细介绍,分享我的经验,希望能对同样对算法有兴趣的朋友有一点点帮助。
首先是欧几里德:
a,b的最大公约数表示为gcd(a,b), 则gcd(a, b)=gcd(b, a%b).
用a%b=a-a/b*b不难证明。重点是扩展欧几里德。
扩展欧几里德:
求ax+by=c是否有整数解及有解时的解。(a, b, c均为整数)。
首先,当c为gcd(a,b)的整数倍时才有整数解。
设a=a1*g, b=b1*g, 故c=ax+by=g*a1*x+g*b1*y,故有解时c必然是g的整数倍。
将a,b,c除g后得到新的ax+by=c(此时a,b互质)
下面先求ax+by=1的解。
考虑ax+by=1............................(1)
又bx+(a%b)y=1........................(2)
=>bx+(a-a/b*b)y=1
=>ay+b(x-a/b*y)=1..................(3)
若x', y'为(2)的解,则可推得(1)的解为x=y', y=x'-a/b*b*y;
在边界时,b=0,a=1(a,b互质),固有一组特解x=1, y=0;
这样就可以求得(1)的一组解,乘一个常数c就是原方程的一组解,进而得到通解。
核心代码如下:
int x, y;
1 void exGcd(int a,int b)
2 { if ( b==0 ) {
3 x=1; y=0;
4 return ;
5 }
6 exGcd(b, a%b);
7 int t;
8 t = x;
9 x = y;
10 y = t - a/b*y;
11 return ;
12 }
除了poj1061,poj2142 ,poj2115也属于这类题。
特别感谢
http://hi.baidu.com/blackstar08/blog/item/5a1b9a2687d07f08918f9d73.html的作者和这篇文章,为我的理解和推理帮助了不少。