青蛙的约会

题目描述

求 x+m*t≡y+n*t (mod l)

题解

将上式

转换一下...

x-y≡(n-m)*t(mod l)

(n-m)*t+l*k=x-y...

然后用扩展欧几里得求...

因为我们用扩展欧几里得求出的是(n-m)*t+l*k=gcd(n-m,l)=(x-y)/k;(当 x-y % gcd(n-m,l) ！=0时无解.

所以答案的 t=扩展欧几里得求出的t*(x-y)/gcd(n-m,l)

又因为要求是最小正整数解..

x=(x0%（b/gcd(a,b))+b/gcd(a,b))%(b/gcd(a,b))即为x的最小整数解。

至于为什么..戳这里

代码