[問題] online judge 上一題如何加速運算?

看板C_and_CPP作者 (克里斯)時間6年前 (2017/07/29 19:31), 6年前編輯推噓8(8推 0噓 20→)
留言28則, 10人參與, 最新討論串1/1
題目： 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://www.ptt.cc/bbs/C_and_CPP/M.1501327883.A.43D.html
推
07/29 20:00, , 1F
從中位數來推呢? 連續n個相加=N 則中位m*n=N
07/29 20:00, 1F
→
07/29 20:02, , 2F
如果連續偶數個則中位數會是x.5 會變(2m+1)*n/2=N
07/29 20:02, 2F
→
07/29 20:04, , 3F
所以當(int)(2*N/n) * n = 2*N時，會有連續正整數之和=N
07/29 20:04, 3F
→
07/29 20:15, , 4F
連續n個數相加最小為n*(n+1)/2，當>N時就可以結束迴圈了
07/29 20:15, 4F
感謝回覆 中位數想法好像不錯！！ 我來想一下～
→
07/29 21:10, , 5F
從d開始加n項的結果是n(d+(n-1)/2)=N
07/29 21:10, 5F
→
07/29 21:11, , 6F
所以項數n必須是N的因數而且是偶數\
07/29 21:11, 6F
→
07/29 21:14, , 7F
上面推的有點bug n不限於偶數 而若n是奇數則n必是N的因數
07/29 21:14, 7F
→
07/29 21:15, , 8F
n是偶數則(n/2)必是N的因數
07/29 21:15, 8F
推
07/29 21:28, , 9F
稍微推了一下發現這好像等同於求質因數的個數
07/29 21:28, 9F
→
07/29 21:38, , 10F
寫錯了，是n-1要是偶數，因為(n-1)/2要是整數
07/29 21:38, 10F
推
07/29 21:44, , 11F
剛好版主不在，提醒一下你這篇應該發在 Prob_Solve
07/29 21:44, 11F
感謝s大提醒！ 之後會發在正確的地方！.此外用了中位數的算法還是無法在時間限制 內完成,看來我還是太弱了Orz 另有個自學新手的疑問: 像online judge這樣的超過時間限制狀況在實際應用面上常見嗎？ 是否一定得想到有辦法克服為止,還是程式測驗僅是為了競賽,實際上太過鑽牛角尖？ 希望有大大稍微開示一下（一直解不開根本無法好好入睡...像有什麼事情未完成一樣）
推
07/30 10:52, , 12F
(N-(1+2))%3 == 0 這是不是跟 N%3 == 0 一樣？
07/30 10:52, 12F
樓上c大有點不一樣喔 前面意思是 N-3為3 的倍數,後面是N為3的倍數 ※ 編輯: ddchris (1.200.224.119), 07/30/2017 11:00:46
推
07/30 12:43, , 13F
先做質因數分解，找因數是否為合法中位數（略過偶數）
07/30 12:43, 13F
→
07/30 12:43, , 14F
。再找所有偶數除以N是否為合法中位數。
07/30 12:43, 14F
推
07/30 13:37, , 15F
N 會大到 10^18, 基本上只能推公式來解了
07/30 13:37, 15F
→
07/30 13:39, , 16F
因為 CPU 時脈一般是 GHz 等級的
07/30 13:39, 16F
→
07/30 13:41, , 17F
不過上面很多人把解法推完了QQ
07/30 13:41, 17F
推
07/30 13:46, , 18F
然後時間限制問題 現實中只要老闆問你明天跑不跑得
07/30 13:46, 18F
→
07/30 13:46, , 19F
完 可以回答是跟否就夠了......
07/30 13:46, 19F
感謝超長整數大回應～（這id也太酷..應該很少人能比你長了(? 看來我還是建立完整的程式寫作觀念, 有多的閒暇時間再來做題目！ ※ 編輯: ddchris (1.200.224.119), 07/30/2017 15:14:05 ※ 編輯: ddchris (1.200.224.119), 07/30/2017 15:15:42
→
07/30 16:24, , 20F
n-3是3的倍數->n是三的變數吧
07/30 16:24, 20F
→
07/30 21:52, , 21F
這個問題好像可以變成所有奇因數的個數再減一
07/30 21:52, 21F
→
07/30 21:58, , 22F
也就是說先把數字除 2 除到變奇數，再質因數分解算因數
07/30 21:58, 22F
→
07/30 22:00, , 23F
個數，最後減一。不知道有沒有比較快的演算法XD
07/30 22:00, 23F
推
07/31 00:06, , 24F
超過時間限制在軟體工作是會遇到的，比如說路徑搜尋。
07/31 00:06, 24F
→
07/31 00:06, , 25F
就空間(記憶體)與時間的取捨
07/31 00:06, 25F
→
08/01 11:13, , 26F
乍看好像是求有幾個質因數的變體
08/01 11:13, 26F
→
08/01 11:13, , 27F
所以就先質因數分解，然後指數加１相乘？
08/01 11:13, 27F
→
08/01 11:41, , 28F
300=2^2*3*5^2 => 2倍數不看 => (1+1)*(2+1)-1=5
08/01 11:41, 28F
‣ 更多 ddchris 的文章
文章代碼(AID): #1PV78BGz (C_and_CPP)