原题
http://poj.org/problem?id=1061
解法
此题用扩展欧几里得计算
(n-m) X ≡ (x-y) (mod l) 的最小正整数解
即(n-m) X + l * Y = (x-y)
贝祖定理: ax + by = m 有整数解时当且仅当m是gcd(a,b)的倍数。
用扩展欧几里得能算出ax + by = gcd(a,b)的一个特解
此特解乘上m / gcd(a,b)得到的就是ax + by = m的特解
所有的解x mod (b/gcd(a,b))同余
所有的解y mod (a/gcd(a,b))同余
参考
https://blog.csdn.net/ccnuacmhdu/article/details/79415284
https://www.cnblogs.com/xeoncdy/p/7265419.html
https://blog.csdn.net/sun897949163/article/details/51894372
https://blog.csdn.net/yoer77/article/details/69568676
1 |
|