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

首先是欧几里德：
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;

除了poj1061，poj2142 ，poj2115也属于这类题。

特别感谢http://hi.baidu.com/blackstar08/blog/item/5a1b9a2687d07f08918f9d73.html的作者和这篇文章，为我的理解和推理帮助了不少。