一道与扩展欧几里得算法有关的ACM题的疑问POJ1061的那道青蛙的约会那道题.我对扩展欧几里得算法不太懂,然后看了很多博客.,他们都总结方法为：关于ax+by=c,令te=gcd(a,b),然后a'=a/te,b'=b/te,c'=c/te

Question

一道与扩展欧几里得算法有关的ACM题的疑问
POJ 1061的那道青蛙的约会那道题.我对扩展欧几里得算法不太懂,然后看了很多博客.,他们都总结方法为：关于ax+by=c,令te=gcd(a,b),然后a'=a/te,b'=b/te,c'=c/te,求a'x+b'y=c'的一个特解x0,y0,所有整数解为：x = n' *
x0 + b' * t,y = n' * y0 - a' * t
(t=0,1,2,……),然后当x0

Answer 1

为了求 最小的正整数解啊. x0是一个特解, 那么 （X0 %b） 也是他的一个解.