切換
舊版
前往
大廳
主題

ZeroJudge - f070: 1. 韓信點兵 (HanXin) 解題心得

Not In My Back Yard | 2020-06-11 00:08:40 | 巴幣 0 | 人氣 1015

題目連結:


題目大意:
輸入有三列,每列給定兩正整數 a 、 b (1 < a 、 b < 300),代表士兵每 a 個一組最後會剩下 b 人。保證每列的 a 值互質。

請找到一個最小的 m (1 ≦ m ≦ 2 × 10 ^ 6)值滿足給定的三個關係式。


範例輸入:
範例輸入一:
3 2
5 3
7 2

範例輸入二:
7 2
9 5
13 7

範例輸入三:
251 69
191 58
241 81


範例輸出:
範例輸出一:
23

範例輸出二:
527

範例輸出三:
48763


解題思維:
因為 m 值夠小,加上只有一筆測試資料。所以其實可以從 1 跑到 2 × 10 ^ 6 ,看哪個值符合就輸出。

但是這種餘數的問題有經典的解法——中國剩餘定理(見維基)。
 
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作