洛谷 P1516 青蛙的約會 解題報告

擴充歐幾裡得

P1516 青蛙的約會

兩隻青蛙在網上相識了，它們聊得很開心，于是覺得很有必要見一面。它們很高興地發現它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。可是它們出發之前忘記了一件很重要的事情，既沒有問清楚對方的特征，也沒有約定見面的具體位置。不過青蛙們都是很樂觀的，它們覺得隻要一直朝着某個方向跳下去，總能碰到對方的。但是除非這兩隻青蛙在同一時間跳到同一點上，不然是永遠都不可能碰面的。為了幫助這兩隻樂觀的青蛙，你被要求寫一個程式來判斷這兩隻青蛙是否能夠碰面，會在什麼時候碰面。

我們把這兩隻青蛙分别叫做青蛙A和青蛙B，并且規定緯度線上東經0度處為原點，由東往西為正方向，機關長度1米，這樣我們就得到了一條首尾相接的數軸。設青蛙A的出發點坐标是x，青蛙B的出發點坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩隻青蛙跳一次所花費的時間相同。緯度線總長L米。現在要你求出它們跳了幾次以後才會碰面。

輸入隻包括一行5個整數\(x\)，\(y\)，\(m\)，\(n\)，\(L\)

其中\(0<x≠y<=2000000000\)，\(0 < m,n < =2000000000\)，\(0 < L < =2100000000\)。

輸出碰面所需要的天數，如果永遠不可能碰面則輸出一行"Impossible"。

exgcd還是有不少小細節的，以前沒做過題不知道

首先 我們需要解同餘方程

\(nx+a \equiv mx+b \ (mod \ l)\)

移項 \((n-m)x \equiv b-a \ (mod \ l)\)

我們確定\((n-m)\)是正的，因為待會要用擴歐

等價于不定方程 \((n-m)x-ly=b-a\)

令 \(q=n-m,p=-l,d=b-a\)

即\(qx+py=d\)

根據裴蜀定理，有解的判定為 \(gcd(q,p)|d\)

剩下的就是擴充歐幾裡得的事情了

通解為 模 \(l/gcd(q,p)\) 意義下的

為什麼呢？

假設我們已經得到特解\(x_0\)

則設有通解\(x=x_0+kt\),\(k\)為周遊的整數，我們要求出\(t\)

帶回原式

\(py=-q(x_0+kt)+d\)

把\(p\)除過去，保證\(y\)為整數

因為\(p|d-qx_0\)(我們已經解出了這個方程)

是以我們隻需要滿足\(p|qkt\)即可

發現\(t\)需要補充\(p/gcd(q,p)\)以外的部分

而\(p=-l\)

是以通解為 模 \(l/gcd(q,p)\) 意義下的

Code:

2018.8.8