聚會編程題
發布時間: 2024-05-04 04:02:41
這道題目是經典的拓展歐幾里德問題,如果沒有聽說過這類問題的解法的話可以去下面這個網站學習下 http://hi..com/wwt14/item/f6b53503e2b65f2ca0312df7
接下來講下思路:
首先我們假設經過 t 時間之後相遇
就有 x+at mod L= y+bt mod L
即 t(a-b) mod L = y-x
變型為 t*(a-b) - p*L=y-x 其中 (a-b) 和 L已知
我們設 (a-b)=A -L=B y-x=C
我們就需要求一對t和p使得 A*t+B*p=C 且使 t 盡量小 這就變成了一個擴展歐幾里德問題的基本模型
,套用一下拓展歐幾里德問題的解法就可以完成此題了
熱點內容