作者csihcs (非天夜翔)
看板C_and_CPP
标题Re: [问题] 计算一数有几个因数
时间Mon Dec 7 11:56:36 2009
※ 引述《bleed1979 (十三)》之铭言：
: ※ 引述《tw00088437 (喵猫 loves fish)》之铭言：
: : ( *[1m *[m 为色码，可以按 Ctrl+V 预览会显示的颜色 )
: : ( 未必需要依照此格式，文章条理清楚即可 )
: : 遇到的问题： (题意请描述清楚)
: : TLE
: : http://zerojudge.tw/ShowProblem?problemid=d433
: : 希望得到的正确结果：
: : 加速
: : 程式跑出来的错误结果：
: : TLE
: : 开发平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
: : dev c++
: : 有问题的code： (请善用置底文标色功能)
: : http://nopaste.csie.org/6e592
: : 先建一仟以下的prime 如果都不能divide = prime
: : 补充说明：
: UVa网站上的出题者曾建议解题的人应该着重於思考解题的方法，减少coding的时间
: 按照你的方法基本上还是可以AC的，也是我一开始不经思考写的code
: 6N+-1的筛法+质因数分解
: http://codepad.org/Shu2oxqo
: AC 2.8s, 非常的慢
: 但实际上这题的解法其实很简单
: 考虑30这个数，他的因数计有1,2,3,5,6,10,15,30
: 1和本身是一定有的，所以一开始30就有1,30这2个因数
: 我们的重点是在2,3,5,6,10,15
: 当我们开始跑for回圈从2到30
: 2,4,6,8,10,12,14,16,18,20,22,24,26,28,30 +1
: 3,6,9,12,14,16,18,21,24,27,30 +1
: 4不会跑到30，略
: 5,10,15,20,25,30 +1
: 6,12,18,24,30 +1
: 7,8,9 略
: 10,20,30 +1
: 11,12,13,14 略
: 15,30 +1
: 16後面略
: 你会发现可以跑到30的数恰恰都是30的因数，+1後也刚好是30因数的个数
: 所以这题只需要两层for回圈, 外层i就由2跑到1000001
: 内回圈由外层i的2倍开始跑起，每经过的index都加1即可
: 这是版本2的code
: http://codepad.org/kzgjYohu
: AC 388ms
: 足足快了7倍
: 仅供参考
: Bleed
先建构 1000 以内的质数表
再把 N 质因数分解
指数+1相乘即为所求。
比方说 300 = 2^2 * 3^1 * 5^2
则因数个数 = (2+1) * (1+1) * (2+1) = 18
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 211.74.9.2
1F：→ bleed1979:这就是版本1的方法，再测资多的时候不太妙 12/07 12:36
2F：推 DJWS:楼上的时间复杂度: O(10^6 * 10^6) 12/07 17:25
3F：→ DJWS:内文的时间复杂度 O(10^3) * 测试资料数 12/07 17:26
4F：→ DJWS:另加上建表时间 O(10^3 * sqrt(10^3)) 12/07 17:27
5F：→ DJWS:我想测试资料数要比 O(10^9) 还多，才会像一楼所说的不太妙。 12/07 17:28
6F：→ bleed1979:要精算的话DP解时间复杂度约1.25*10^11 12/07 20:47
7F：→ bleed1979:另外，两种解的一次运算根本不等价 12/07 20:49
8F：→ bleed1979:最後我特地测了测资刚好是10^6以上 拿了OLE 12/07 20:56
9F：推 tw00088437:A...小弟我就是第一次作1000以下的质表然後分解 12/07 21:13
10F：→ tw00088437:然後就TLE GET 12/07 21:13
12F：→ bleed1979:这方法搭配测资如果能快到500ms以下那我也认了 12/07 21:24
13F：推 ledia:怎麽时间复杂度里面都放常数呀... 那不就变成 constant 了XD 12/08 10:25
14F：推 ledia:btw, 原 po 的回圈可以加一些 cut 12/08 10:32
15F：→ ledia:有些数已经是质数就别拿去除了(看 ans[g]) 12/08 10:34
16F：→ ledia:bleed 的复杂度是 O(nlng+K) 12/08 10:34
17F：→ ledia:原 post 的大约 O(n^(1.5) * K) 吧 12/08 10:35
18F：→ ledia:更正, 原 post 的大约 O(n^(1.5) + K) 吧 12/08 10:35
19F：推 DJWS:楼上可能没有仔细看bleed的程式码，应该是O(n^2 + K) 12/08 12:56
20F：→ DJWS:内文的则是 O(n^0.75 + K * n^0.5) K是资料笔数 12/08 12:59
21F：→ DJWS:至於bleed在推文中贴的程式码，则是跟内文讲的方法一样。 12/08 13:05
22F：→ DJWS:不过bleed是用筛法建质数表，所以变成 O(nlogn + K * n^0.5) 12/08 13:07
23F：推 DJWS:更正，是 O((n^0.5)*log(n^0.5) + K * n^0.5) 12/08 13:11
24F：推 ledia:我说的是版本 2 喔... 应该是 O(nlgn) 没有错 12/08 22:02
25F：推 DJWS:是我错了，版本2的确是O(nlgn)。另外调和数列是O(lgn)。 12/08 23:16