Re: [問題] 計算一數有幾個因數
※ 引述《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
12/07 12:36, 1F
推
12/07 17:25, , 2F
12/07 17:25, 2F
→
12/07 17:26, , 3F
12/07 17:26, 3F
→
12/07 17:27, , 4F
12/07 17:27, 4F
→
12/07 17:28, , 5F
12/07 17:28, 5F
→
12/07 20:47, , 6F
12/07 20:47, 6F
→
12/07 20:49, , 7F
12/07 20:49, 7F
→
12/07 20:56, , 8F
12/07 20:56, 8F
推
12/07 21:13, , 9F
12/07 21:13, 9F
→
12/07 21:13, , 10F
12/07 21:13, 10F
→
12/07 21:24, , 11F
12/07 21:24, 11F
→
12/07 21:24, , 12F
12/07 21:24, 12F
推
12/08 10:25, , 13F
12/08 10:25, 13F
推
12/08 10:32, , 14F
12/08 10:32, 14F
→
12/08 10:34, , 15F
12/08 10:34, 15F
→
12/08 10:34, , 16F
12/08 10:34, 16F
→
12/08 10:35, , 17F
12/08 10:35, 17F
→
12/08 10:35, , 18F
12/08 10:35, 18F
推
12/08 12:56, , 19F
12/08 12:56, 19F
→
12/08 12:59, , 20F
12/08 12:59, 20F
→
12/08 13:05, , 21F
12/08 13:05, 21F
→
12/08 13:07, , 22F
12/08 13:07, 22F
推
12/08 13:11, , 23F
12/08 13:11, 23F
推
12/08 22:02, , 24F
12/08 22:02, 24F
推
12/08 23:16, , 25F
12/08 23:16, 25F
討論串 (同標題文章)