作者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
→ tiyun:題目是問這個嗎? 怎麼跟我看到的不一樣? 05/03 21:00
推 gba356:這個在討論區有人貼了一個連結，說明題目可以轉化為原 PO 05/03 21:03
推 Fenikso:質數不超過1e6的假設真是太邪惡了XDD 05/03 21:25
→ bleed1979:準確來說 應該是沒有2個超過10E6的質因數相乘 05/03 21:26
→ bleed1979:因為除不盡的數都把他當做質數了 05/03 21:26
推 DJWS:我看rank list有滿多人都是一秒之內通過的 應該有更妙的方法 05/03 21:28
推 gba356:討論區有一篇說有三個結果，然後說不要再寫信問他了XD 05/03 21:29
推 Fenikso:剛剛試了一下 找1e6以內所有奇質數,用篩的 0.5秒過 05/03 21:44
推 DJWS:感謝樓上...難道大家都是這樣AC的？ XD 05/03 23:42