作者bleed1979 (十三)
看板C_and_CPP
标题Re: [ACM ] 10290 {Sum+=i++} to Reach N
时间Sun May 3 20:38:26 2009
※ 引述《DJWS (...)》之铭言：
: 这一题会用到质因数分解
: 我本想使用 Pollard's rho algorithm
: 不过N的范围实在太大了 (9*10^14)
: 运算过程当中无法把数值直接放进一个64bit的整数里
: 这条路不知可不可行...
: 想请教各位是什麽方式通过这题的？
唉 这题我的程式只能刚好通过ACM UVa上的测资
只能说测资不够刁钻 如果我将程式修正的话 就会TLE
先讲解这题在问什麽
这题要求某个数 他的奇因数有几个
以30来说 1, 2, 3, 5, 6, 10, 15, 30
所以答案是 4 ( 1, 3, 5, 15 )
比较快的方法就是求奇质因数指数 + 1後相乘
30 = 2^1 * 3^1 * 5^1
所以答案为 (1 + 1) * (1 + 1) = 4
如果有某个数的质因数分解是 2^3 * 3^2 * 7^1
答案为 ( 2 + 1 ) * ( 1 + 1 ) = 6
质因数2可以完全不管他
所以我们得到题目输入的n时
先把所有的2除尽
for( ; n > 1 && n % 2 == 0; n /= 2 );
之後的n开始质因数分解并对奇质因数的指数下功夫
如果还在
for(k = 3; k <= n; k += 2)
一定是TLE 我们的k一次跳一定是跳质数
所以又回到求质数的老问题
不管用任何方法总之要先求出一群质数并放入阵列
range到9E14 所以理论上要求到3E7的质数才准
而我赌测资不会超过10E6的质数
所以我把range下修到10E6
如此才AC的 AC秒数是2.150 也差点TLE了
如果我要修正程式到3E7的话 还是TLE
大致上是这样
至於质因式分解这个大家都很熟才对
附带一提
PKU OJ 2140 和这一题一模一样
但他的测资只到10E7 可以轻松巴假的
短码达人这本书有提到
不过该书里面的code对这题来说只是code短而已 速度上还是很慢的
Pollard's rho algorithm
这个演算法的缺点在於如果数是composite的话
也就是这个数是好几个质数的乘积
就要花很多时间去换 c 来run这个演算法
我用大数实作这个演算法上传 还是TLE
Bleed
--
World of bleed1979
http://bleed1979.myweb.hinet.net/
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.168.133.230
1F：→ tiyun:题目是问这个吗? 怎麽跟我看到的不一样? 05/03 21:00
2F：推 gba356:这个在讨论区有人贴了一个连结，说明题目可以转化为原 PO 05/03 21:03
4F：推 Fenikso:质数不超过1e6的假设真是太邪恶了XDD 05/03 21:25
5F：→ bleed1979:准确来说 应该是没有2个超过10E6的质因数相乘 05/03 21:26
6F：→ bleed1979:因为除不尽的数都把他当做质数了 05/03 21:26
7F：推 DJWS:我看rank list有满多人都是一秒之内通过的 应该有更妙的方法 05/03 21:28
8F：推 gba356:讨论区有一篇说有三个结果，然後说不要再写信问他了XD 05/03 21:29
9F：推 Fenikso:刚刚试了一下 找1e6以内所有奇质数,用筛的 0.5秒过 05/03 21:44
11F：推 DJWS:感谢楼上...难道大家都是这样AC的？ XD 05/03 23:42