切換
舊版
前往
大廳
主題

ZeroJudge - d648: 國際象棋(knight) 解題心得

Not In My Back Yard | 2019-10-22 22:50:06 | 巴幣 2 | 人氣 134

題目連結:


題目大意:
給定兩正整數 n 、m (1 ≦ n 、 m ≦ 10 ^ 8,當 n = m = 0 時代表輸入結束),代表一個「廣義馬」的棋子可以水平(垂直)移動 n 單位、垂直(水平)移動 m 單位(原本象棋的馬走「日」字形,所以是 n = 1 、m = 2 的馬)。

現在這個馬從原點(0, 0)開始,走在無限大的座標平面上。試問這個馬是不是可以抵達任意格子。可以的話,輸出「YES」;反之,輸出「Impossible」。



範例輸入:
1 2
2 2
0 0


範例輸出:
YES
Impossible


解題思維:
可以看到如果 n 、 m 都是奇數(偶數),則不管怎麼走 x 、 y 座標都會是奇數(偶數)。因此當 n 、 m 奇偶性相同時,一定無法走到所有的點。

接著,可以看到所有的點的走法都類似於從(0, 0)走到(0, 1)的走法(包含鏡射)。所以對於從(0, 0)到(a, b) 的走法為(0, 0) → (0, 1) → (0, 2)→ …… → (0, b) → (1, b) → (2, b) → …… → (a, b),但是這個條件建立在上面的前提(即 n 、 m 兩者不能同為奇數或偶數)。

而要滿足可以從(0, 0)走到 (0, 1)代表方程式
an + bm = 1
可以找到整數的(a, b)數對之解。而此方程式有整數解若且唯若 n 跟 m 的最大公因數為 1 (也就是 n 與 m 互質)。

因此,要走到所有點的話, n 、 m 要互質且奇偶性相反。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作