ProjectEuler 590 - Solution

經由手算，得出下列公式：$$H(n) = \sum_{d|n} \mu(d)* (2^{\sigma_0(\frac{n}{d})}-1) $$
其中$\mu()$是莫比烏斯函數(mobius function)，$\sigma_0()$是因數個數的函數
例如 $\sigma_0(6)=4$，因為6有4個因數(divisor)


上述公式也可寫成$H(n) = \sum_{d|n} \mu(\frac{n}{d})* (2^{\sigma_0(d)}-1) $，意義是一樣的。

莫比烏斯函數$\mu(n)$只有在n為squarefree的時候才不為零。
所以 又可以寫成$H(n) = \sum_{d|n, d\in {squarefree}} \mu(d)* (2^{\sigma_0(\frac{n}{d})}-1) $

當n > 1時，上述公式的mobius函數的正負項數是一樣多的，所以-1終究會被消掉，又可以進一步化簡為$H(n) = \sum_{d|n, d\in {squarefree}} \mu(d)*2^{\sigma_0(\frac{n}{d})} $ for n > 1

雖然寫出公式了，但H(n)展數的項數為$2^{x}$，其中x是n的質因數個數。

L(50000)=2¹⁵3⁹5⁶7⁵(11·13)⁴(17·...·31)³(37·...·223)²(227·...·49999)有5133個質因數，所以 HL(50000)= H(2¹⁵3⁹5⁶7⁵(11·13)⁴(17·...·31)³(37·...·223)²(227·...·49999) )展開後一共有$2^{5133}$項，一項一項求當然不可能，最後還是用DP解掉這一題。

Coding實在不是很順利，提交答案一直吃WA，也許是題目沒給中型的測資，只給了一個很小的HL(4)=44當測資。WA了半天也不知道自己錯在哪？最後火大， 寫了一個Brute-force的程式來驗證，發現在HL(17)的時候就錯掉了，於是又花了一點時間Debug，終於解出來了。花了五小時又十二分拿到第19名。實在很弱，不過至少在前20。我的目標只有前20而已。

這篇拉拉雜雜寫了一堆。其實只是為了測試我的Blog剛裝的LaTex而已。