作者ddchris (克里斯)
看板C_and_CPP
標題[問題] online judge 上一題如何加速運算?
時間Sat Jul 29 19:31:19 2017
題目：
https://zerojudge.tw/ShowProblem?problemid=c226
程式碼(Code)：(請善用置底文網頁, 記得排版)
http://codepad.org/AlD2neR4
補充說明(Supplement)：
題目大意是對於某一正整數 N,
小於 N（1~ N-1）之連續正整數的和恰好等於 N 有幾組?
假設最小數字為 d 可能狀況為 d+(d+1)=N,d+(d+1)+(d+2)=N,
d+(d+1)+(d+2)+(d+3)=N 以下類推...
等同 2d+1=N,3d+(1+2)=N,4d+(1+2+3)=N ...
所以 (N-1)%2 ==0 或 (N-(1+2))%3 == 0 或...其中一項成立及代表一組解
程式碼跑起來也OK 但是時間超過了 online judge的限制,所以想問一下這邊大神們
是否有更有效率算法或加速的方式？ 感恩！
程式新手還請鞭小力一點 > <
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.224.119
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1501327883.A.43D.html
1F：推 Richun: 從中位數來推呢? 連續n個相加=N 則中位m*n=N 07/29 20:00
2F：→ Richun: 如果連續偶數個則中位數會是x.5 會變(2m+1)*n/2=N 07/29 20:02
3F：→ Richun: 所以當(int)(2*N/n) * n = 2*N時，會有連續正整數之和=N 07/29 20:04
4F：→ Richun: 連續n個數相加最小為n*(n+1)/2，當>N時就可以結束迴圈了 07/29 20:15
感謝回覆 中位數想法好像不錯！！ 我來想一下～
5F：→ Littlechozy: 從d開始加n項的結果是n(d+(n-1)/2)=N 07/29 21:10
6F：→ Littlechozy: 所以項數n必須是N的因數而且是偶數\ 07/29 21:11
7F：→ Richun: 上面推的有點bug n不限於偶數 而若n是奇數則n必是N的因數 07/29 21:14
8F：→ Richun: n是偶數則(n/2)必是N的因數 07/29 21:15
9F：推 Richun: 稍微推了一下發現這好像等同於求質因數的個數 07/29 21:28
10F：→ Littlechozy: 寫錯了，是n-1要是偶數，因為(n-1)/2要是整數 07/29 21:38
11F：推 s25g5d4: 剛好版主不在，提醒一下你這篇應該發在 Prob_Solve 07/29 21:44
感謝s大提醒！ 之後會發在正確的地方！.此外用了中位數的算法還是無法在時間限制
內完成,看來我還是太弱了Orz
另有個自學新手的疑問:
像online judge這樣的超過時間限制狀況在實際應用面上常見嗎？
是否一定得想到有辦法克服為止,還是程式測驗僅是為了競賽,實際上太過鑽牛角尖？
希望有大大稍微開示一下（一直解不開根本無法好好入睡...像有什麼事情未完成一樣）
12F：推 chuegou: (N-(1+2))%3 == 0 這是不是跟 N%3 == 0 一樣？ 07/30 10:52
樓上c大有點不一樣喔 前面意思是 N-3為3 的倍數,後面是N為3的倍數
※ 編輯: ddchris (1.200.224.119), 07/30/2017 11:00:46
13F：推 kevin85421: 先做質因數分解，找因數是否為合法中位數（略過偶數） 07/30 12:43
14F：→ kevin85421: 。再找所有偶數除以N是否為合法中位數。 07/30 12:43
15F：推 longlongint: N 會大到 10^18, 基本上只能推公式來解了 07/30 13:37
16F：→ longlongint: 因為 CPU 時脈一般是 GHz 等級的 07/30 13:39
17F：→ longlongint: 不過上面很多人把解法推完了QQ 07/30 13:41
18F：推 longlongint: 然後時間限制問題 現實中只要老闆問你明天跑不跑得 07/30 13:46
19F：→ longlongint: 完 可以回答是跟否就夠了...... 07/30 13:46
感謝超長整數大回應～（這id也太酷..應該很少人能比你長了(?
看來我還是建立完整的程式寫作觀念,
有多的閒暇時間再來做題目！
※ 編輯: ddchris (1.200.224.119), 07/30/2017 15:14:05
※ 編輯: ddchris (1.200.224.119), 07/30/2017 15:15:42
20F：→ fatrabitree: n-3是3的倍數->n是三的變數吧 07/30 16:24
21F：→ Sanvean: 這個問題好像可以變成所有奇因數的個數再減一 07/30 21:52
22F：→ Sanvean: 也就是說先把數字除 2 除到變奇數，再質因數分解算因數 07/30 21:58
23F：→ Sanvean: 個數，最後減一。不知道有沒有比較快的演算法XD 07/30 22:00
24F：推 noodleT: 超過時間限制在軟體工作是會遇到的，比如說路徑搜尋。 07/31 00:06
25F：→ noodleT: 就空間(記憶體)與時間的取捨 07/31 00:06
26F：→ HolyBugTw: 乍看好像是求有幾個質因數的變體 08/01 11:13
27F：→ HolyBugTw: 所以就先質因數分解，然後指數加１相乘？ 08/01 11:13
28F：→ HolyBugTw: 300=2^2*3*5^2 => 2倍數不看 => (1+1)*(2+1)-1=5 08/01 11:41