·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接:http://poj.org/problem?id=1061
这题是拓展欧几里得算法。
裴蜀等式
任何整数a、b和m,关于未知数x和y的线性丢番圆方程(称为裴蜀等式):
ax+by=m
有整数解时当且仅当m是a和b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解,每组解x、y都称为裴蜀数
——引用自维基百科
若方程ax+by=m的一组整数解为(x0,y0),则它的任意整数解都可以写成(x0+kb’,y0-ka’),其中a’=a/gcd(a,b),b’=b/gcd(a,b),k取任意整数
模线线性方程组
ax≡b(mod n)
ax=b+ny
ax-ny=b 进而转化为裴蜀等式
补充:当b等于1时模线性方程组的解是a关于模n的逆,a关于模n的逆存在当且仅当a和n互质,此时方程有唯一解
题目思路
根据题意可以写出等式(x+km)%L=(y+kn)%L
而这样的式子有一个性质a%L=b%L ==> (a+c)%L=(b+c)%L
因而可以得出(k(m-n))%L=(y-x)%L
k(m-n)≡y-x(mod L) 接下来就可以用解模线性方程组的方法来做了
需要注意m-n必须是非负的
1 |
|