POJ1061 青蛙的约会 线性模方程

• wxc971231 发布于
• 1782 收藏

本题知识求一个最小的解。 首先我们易得所有变量满足 x+mt=y+nt(mod l) 转化mt-nt=y-x(mod l) 再转发得(m-n)t=y-x(mod l) 这是一个线性模方程的形式，这里已经可以求解了。  当 （y-x） % GCD(l,(m-n)*t)！=0时无解    原理：用扩展欧几里得求得 ax0=b(mod m)->    ax0=b-my0->    ax0+my0=b...