作者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