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

看板C_and_CPP作者 (非天夜翔)時間15年前 (2009/12/07 03:56), 編輯推噓8(8017)
留言25則, 4人參與, 最新討論串3/3 (看更多)
※ 引述《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

12/07 12:36, , 1F
這就是版本1的方法,再測資多的時候不太妙
12/07 12:36, 1F

12/07 17:25, , 2F
樓上的時間複雜度: O(10^6 * 10^6)
12/07 17:25, 2F

12/07 17:26, , 3F
內文的時間複雜度 O(10^3) * 測試資料數
12/07 17:26, 3F

12/07 17:27, , 4F
另加上建表時間 O(10^3 * sqrt(10^3))
12/07 17:27, 4F

12/07 17:28, , 5F
我想測試資料數要比 O(10^9) 還多,才會像一樓所說的不太妙。
12/07 17:28, 5F

12/07 20:47, , 6F
要精算的話DP解時間複雜度約1.25*10^11
12/07 20:47, 6F

12/07 20:49, , 7F
另外,兩種解的一次運算根本不等價
12/07 20:49, 7F

12/07 20:56, , 8F
最後我特地測了測資剛好是10^6以上 拿了OLE
12/07 20:56, 8F

12/07 21:13, , 9F
A...小弟我就是第一次作1000以下的質表然後分解
12/07 21:13, 9F

12/07 21:13, , 10F
然後就TLE GET
12/07 21:13, 10F

12/07 21:24, , 11F
http://codepad.org/gSmMNKnn 版本1修改過後AC 1.3s
12/07 21:24, 11F

12/07 21:24, , 12F
這方法搭配測資如果能快到500ms以下那我也認了
12/07 21:24, 12F

12/08 10:25, , 13F
怎麼時間複雜度裡面都放常數呀... 那不就變成 constant 了XD
12/08 10:25, 13F

12/08 10:32, , 14F
btw, 原 po 的迴圈可以加一些 cut
12/08 10:32, 14F

12/08 10:34, , 15F
有些數已經是質數就別拿去除了(看 ans[g])
12/08 10:34, 15F

12/08 10:34, , 16F
bleed 的複雜度是 O(nlng+K)
12/08 10:34, 16F

12/08 10:35, , 17F
原 post 的大約 O(n^(1.5) * K) 吧
12/08 10:35, 17F

12/08 10:35, , 18F
更正, 原 post 的大約 O(n^(1.5) + K) 吧
12/08 10:35, 18F

12/08 12:56, , 19F
樓上可能沒有仔細看bleed的程式碼,應該是O(n^2 + K)
12/08 12:56, 19F

12/08 12:59, , 20F
內文的則是 O(n^0.75 + K * n^0.5) K是資料筆數
12/08 12:59, 20F

12/08 13:05, , 21F
至於bleed在推文中貼的程式碼,則是跟內文講的方法一樣。
12/08 13:05, 21F

12/08 13:07, , 22F
不過bleed是用篩法建質數表,所以變成 O(nlogn + K * n^0.5)
12/08 13:07, 22F

12/08 13:11, , 23F
更正,是 O((n^0.5)*log(n^0.5) + K * n^0.5)
12/08 13:11, 23F

12/08 22:02, , 24F
我說的是版本 2 喔... 應該是 O(nlgn) 沒有錯
12/08 22:02, 24F

12/08 23:16, , 25F
是我錯了,版本2的確是O(nlgn)。另外調和數列是O(lgn)。
12/08 23:16, 25F
文章代碼(AID): #1B77psme (C_and_CPP)
文章代碼(AID): #1B77psme (C_and_CPP)