这是一道扩展欧几里德的题,对于我这个才学算法半年的新手来说,理解它还是花了不少时间的。下面详细介绍,分享我的经验,希望能对同样对算法有兴趣的朋友有一点点帮助。

首先是欧几里德:
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的作者和这篇文章,为我的理解和推理帮助了不少。