ProjectEuler 362 Squarefree factors - 拼圖

※ [本文轉錄自 chyrliin 信箱]

作者: babufong (嗶嗶) 看板: puzzle
標題: [中譯] ProjectEuler 362 Squarefree factors
時間: Sun Dec 11 15:30:32 2011

362. Squarefree factors

http://projecteuler.net/problem=362


來看看 54 這個數字

54 可以拆成 7 種全然不同的一個或多個因數相乘的組成方法，而這些因數都大於 1

如：54 , 2 X 27 , 3 X 18 , 6 X 9 , 3 X 3 X 6 , 2 X 3 X 9 和 2 X 3 X 3 X 3

如果我們要求這些因數都要是「無平方數因數」的數所組成，那就只剩下 2 種組法：

3 X 3 X 6 和 2 X 3 X 3 X 3


Fsf(n) 為 n 有幾種上述條件的方法去組成，所以 Fsf(54) = 2

S(n) 為 ΣFsf(k) , k = 2 到 n

已知 S(100) = 193


請求出 S(10000000000)

--