对于方程:ax≡b(mod m),a,b,m都是整数,求解x的值. 例题:poj 1061 青蛙的约会 符号说明: mod表示:取模运算 ax≡b(mod m)表示:ax-b≡0(mod m),即同余 gcd(a,b)表示:a和b的最大公约数 分析过程: 问题一:求解最大公约数. 古老的解法是欧几里德法,即辗转相除法:gcd(a,b)=gcd(b,a mod b). 问题二:存在x,y使得ax+by=gcd(a,b); ax+by=gcd(a,b)=gcd(b,a mod b) =b*x +(a-[ab]*b)*y ([]表示取整) =a*y +b*(x -[ab]*y ) 则: x=y ; y=x -[ab]*y ; 问题三:ax≡b(mod m)的求解. 首先,gcd(a,m)必须整除b,否则方程无解. 其次,当gcd(a,m)=1时,存在x0,y0使得x0*a+y0*m=1,令x=b*x0,然后mod m.可得在[0,m)上的唯一解. 最后,当d=gcd(a,m)1时,考虑方程:ad *x=bd (mod md).可得一解x属于[0,md).原方程有d个解:x,x+md,x+2md..,x+(d-1)md. 程序如下: #incl deiostream str ct triple { int gcd,x,y;