切換
舊版
前往
大廳
主題

ZeroJudge - b230: TOI2009 第二題:方便數 解題心得

Not In My Back Yard | 2020-07-08 00:29:17 | 巴幣 0 | 人氣 254

題目連結:


題目大意:
「方便數」(Convenient Numbers)、「合適數」(Suitable Numbers)或稱「艾多尼數」(Idoneal Numbers)定義為一個正整數 N 不能表示為
N = ab + bc + ca
其中, a 、 b 、 c 為三個相異正整數。

而「不是」方便數的正整數則可以找到一組(a, b, c)滿足上面的式子。可以看到前十五個方便數為 1 、 2 、 3 、 4 、 5 、 6 、 7 、 8 、 9 、 10 、 12 、 13 、 15 、 16 、 18 。

現給定一正整數 k (0 < k ≦ 65),求第 k 小的方便數為何?



範例輸入:
範例輸入一:
5

範例輸入二:
11


範例輸出:
範例輸出一:
5

範例輸出二:
12


解題思維:
窮舉可能的 (a, b, c) 數組,計算 ab + bc + ca ,藉此來篩掉那些不是方便數的數字。

假設現在是要篩掉 2000 以內的非方便數數字,則 a 從 1 跑到 1998 、 b 從 a + 1 跑到 1999 、 c 從 b + 1 跑到 2000 。這樣便可以確保窮舉到所有可能的數組並消除了排列組合後的數組(單純重新排列 a 、 b 、 c 並不影響式子的值)。

可以看到第 65 個方便數其實非常地小,其值為 1848 。因此就掃過一次 1 ~ 2000 的數找出那些沒有被窮舉過程產生的式子之值(ab + bc + ca)所覆蓋到的數字,即是所求的方便數。輸出給定的數字 k 所對應的第 k 小即可。

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

創作回應

更多創作