切換
舊版
前往
大廳
主題

ZeroJudge - d439: 11226 - Reaching the fix-point. 解題心得

Not In My Back Yard | 2020-06-28 01:14:49 | 巴幣 2 | 人氣 109

題目連結:


題目大意:
定義 sopf(n) 為 n 的質因數之和。例如 4 = 2 × 2 、 5 = 5 、 6 = 2 × 3 ,則 sopf(4) = 2 + 2 = 4 、 sopf(5) = 5 、 sopf(6) = 2 + 3 = 6 。

對於 sopf 函數,我們可以進行迭代,如 sopf(sopf(n)) 、 sopf(sopf(sopf(n))) 等等。而這個過程必定會遇到一數 f ,使得 sopf(f) = f 。例如我們從 8 開始,sopf(8) = 6 、 sopf(6) = 5 、 sopf(5) = 5 ,迭代 3 次的 sopf 就來到了一個定點 f = 5 。

再定義一函數 lsopf(n) 為數字 n 需要迭代多少次才對抵達定點 f 。

輸入第一列給定一正整數 T (1 ≦ T ≦ 150),代表有 T 筆測試資料,每筆佔一列。每列給定兩正整數 n 、 m (1 < n 、 m ≦ 500000),求 n(含)~ m(含)之間的數字,何者的 lsopf 函數值最大。輸出格式參見範例輸出。



範例輸入:
2
2 10
11 20


範例輸出:
Case #1:
3
Case #2:
4


解題思維:
可以看到所有的質數自身就是定點,另外還有一個特別的定點 f = 4,唯一一個非質數定點(因為其他數字之質因數之和小於自身)。

而直接建一個 2 ~ 500000 的 lsopf 函數值之表。接著就對於任何的 n 、 m 區間就看其中的數字何者函數值最大。 值得注意的是,題目並沒有保證 n < m ,有可能是 m > n 或是相等。

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

創作回應

更多創作