Re: [問題] 計算一數有幾個因數
※ 引述《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
--
World of bleed1979
http://bleed1979.myweb.hinet.net/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97
推
12/06 21:35, , 1F
12/06 21:35, 1F
推
12/06 22:32, , 2F
12/06 22:32, 2F
→
12/06 22:32, , 3F
12/06 22:32, 3F
→
12/06 22:32, , 4F
12/06 22:32, 4F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
