Re: [問題] 計算一數有幾個因數

[csihcs (非天夜翔)]

※ 引述《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
→ bleed1979:這就是版本1的方法，再測資多的時候不太妙
推 DJWS:樓上的時間複雜度: O(10^6 * 10^6)
→ DJWS:內文的時間複雜度 O(10^3) * 測試資料數
→ DJWS:另加上建表時間 O(10^3 * sqrt(10^3))
→ DJWS:我想測試資料數要比 O(10^9) 還多，才會像一樓所說的不太妙。
→ bleed1979:要精算的話DP解時間複雜度約1.25*10^11
→ bleed1979:另外，兩種解的一次運算根本不等價
→ bleed1979:最後我特地測了測資剛好是10^6以上  拿了OLE
推 tw00088437:A...小弟我就是第一次作1000以下的質表然後分解
→ tw00088437:然後就TLE GET
→ bleed1979:http://codepad.org/gSmMNKnn  版本1修改過後AC 1.3s
→ bleed1979:這方法搭配測資如果能快到500ms以下那我也認了
推 ledia:怎麼時間複雜度裡面都放常數呀... 那不就變成 constant 了XD
推 ledia:btw, 原 po 的迴圈可以加一些 cut
→ ledia:有些數已經是質數就別拿去除了(看 ans[g])
→ ledia:bleed 的複雜度是 O(nlng+K)
→ ledia:原 post 的大約 O(n^(1.5) * K) 吧
→ ledia:更正, 原 post 的大約 O(n^(1.5) + K) 吧
推 DJWS:樓上可能沒有仔細看bleed的程式碼，應該是O(n^2 + K)
→ DJWS:內文的則是 O(n^0.75 + K * n^0.5) K是資料筆數
→ DJWS:至於bleed在推文中貼的程式碼，則是跟內文講的方法一樣。
→ DJWS:不過bleed是用篩法建質數表，所以變成 O(nlogn + K * n^0.5)
推 DJWS:更正，是 O((n^0.5)*log(n^0.5) + K * n^0.5)
推 ledia:我說的是版本 2 喔... 應該是 O(nlgn) 沒有錯
推 DJWS:是我錯了，版本2的確是O(nlgn)。另外調和數列是O(lgn)。