學長的約會XD。

假設 s 回合後會相遇,則有以下方程式

(x+m*s)-(y+n*s) % l = 0

可是這樣沒辦法做事,所以要來調整一下

-> (x+m*s)-(y+n*s) = k*l

-> (x-y)+(m-n)*s = k*l

-> (n-m)*s + k*l = (x-y)

變成 ax+by=gcd(a, b)*k 的樣子,可以用 擴展歐幾里得(exGcd) 解出 (x, y) 一解。

"擴展歐幾里德定理
對於不完全為0 的非負整數a,b,gcd(a,b)表示a,b 的最大公約數,必然存在整
數對 x,y ,使得 gcd(a,b)=ax+by。"....轉載自Baid

只是可能解出來的 ax<0,所以最後要處理一下((ax*(c/g)%b+b)%b)。

我的code

http://snipt.org/zffL3

 

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()