作者chyrliin (企鵝靈)
標題Fw: [中譯] ProjectEuler 362 Squarefree factors
時間Mon Dec 19 19:31:11 2011
※ [本文轉錄自 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)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.224.9.90
1F：推 lighttodie:好酷 12/11 16:55
3F：推 utomaya:如果要跑暴力破解法 應該不會那麼難 12/17 19:49
4F：→ utomaya:不過要跑一分鐘以內 就有點難度 12/17 19:49
5F：→ utomaya:OEIS中已經有說同樣的prime signature 其a(n)是一樣的 12/17 19:51
6F：→ utomaya:所以不必每一個數都去算其a(n), 同樣的prime signature 12/17 19:52
7F：→ utomaya:算一就好, 並存到表格內(應該是Hash)，遇到同樣的prime 12/17 19:54
8F：→ utomaya:signature, 再從hash table取出即可 12/17 19:54
9F：→ utomaya:素數的枚舉，也不用枚舉到10^10即可, 枚舉到10^8即可 12/17 19:57
10F：→ utomaya:大如10^8的素數,假若為p, p*1~p*100其a(n)等於101~101*100 12/17 19:58
11F：→ utomaya:所以只要算出小於(10^10)/1,(10^10)/2,...,(10^10)/100 12/17 20:00
12F：→ utomaya:的素數個數即可 12/17 20:00
13F：→ utomaya:我的方法, 如果是用C++加上現在主流的PC(core i7) 12/17 20:03
14F：→ utomaya:應該是十分鐘以內可以跑出結果 12/17 20:04
※ Deleted by: puzzlez (123.194.45.3) 12/18/2011 20:31:07
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: chyrliin (180.176.101.150), 時間: 12/19/2011 19:31:11
15F：推 babufong:感謝企鵝靈解救文章！ 12/19 19:41
16F：推 LPH66:結果真的是帕索不小心刪掉的...XD 12/19 20:16
17F：推 puzzlez:= = 不過為什麼企鵝靈找得到文章呢？我都找不到..... 12/19 20:35