推 Richun: 從中位數來推呢? 連續n個相加=N 則中位m*n=N 07/29 20:00
→ Richun: 如果連續偶數個則中位數會是x.5 會變(2m+1)*n/2=N 07/29 20:02
→ Richun: 所以當(int)(2*N/n) * n = 2*N時,會有連續正整數之和=N 07/29 20:04
→ Richun: 連續n個數相加最小為n*(n+1)/2,當>N時就可以結束迴圈了 07/29 20:15
感謝回覆 中位數想法好像不錯!! 我來想一下~
→ Littlechozy: 從d開始加n項的結果是n(d+(n-1)/2)=N 07/29 21:10
→ Littlechozy: 所以項數n必須是N的因數而且是偶數\ 07/29 21:11
→ Richun: 上面推的有點bug n不限於偶數 而若n是奇數則n必是N的因數 07/29 21:14
→ Richun: n是偶數則(n/2)必是N的因數 07/29 21:15
推 Richun: 稍微推了一下發現這好像等同於求質因數的個數 07/29 21:28
→ Littlechozy: 寫錯了,是n-1要是偶數,因為(n-1)/2要是整數 07/29 21:38
推 s25g5d4: 剛好版主不在,提醒一下你這篇應該發在 Prob_Solve 07/29 21:44
感謝s大提醒! 之後會發在正確的地方!.此外用了中位數的算法還是無法在時間限制
內完成,看來我還是太弱了Orz
另有個自學新手的疑問:
像online judge這樣的超過時間限制狀況在實際應用面上常見嗎?
是否一定得想到有辦法克服為止,還是程式測驗僅是為了競賽,實際上太過鑽牛角尖?
希望有大大稍微開示一下(一直解不開根本無法好好入睡...像有什麼事情未完成一樣)
推 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
推 kevin85421: 先做質因數分解,找因數是否為合法中位數(略過偶數) 07/30 12:43
→ kevin85421: 。再找所有偶數除以N是否為合法中位數。 07/30 12:43
推 longlongint: N 會大到 10^18, 基本上只能推公式來解了 07/30 13:37
→ longlongint: 因為 CPU 時脈一般是 GHz 等級的 07/30 13:39
→ longlongint: 不過上面很多人把解法推完了QQ 07/30 13:41
推 longlongint: 然後時間限制問題 現實中只要老闆問你明天跑不跑得 07/30 13:46
→ 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
→ fatrabitree: n-3是3的倍數->n是三的變數吧 07/30 16:24
→ Sanvean: 這個問題好像可以變成所有奇因數的個數再減一 07/30 21:52
→ Sanvean: 也就是說先把數字除 2 除到變奇數,再質因數分解算因數 07/30 21:58
→ Sanvean: 個數,最後減一。不知道有沒有比較快的演算法XD 07/30 22:00
推 noodleT: 超過時間限制在軟體工作是會遇到的,比如說路徑搜尋。 07/31 00:06
→ noodleT: 就空間(記憶體)與時間的取捨 07/31 00:06
→ HolyBugTw: 乍看好像是求有幾個質因數的變體 08/01 11:13
→ HolyBugTw: 所以就先質因數分解,然後指數加1相乘? 08/01 11:13
→ HolyBugTw: 300=2^2*3*5^2 => 2倍數不看 => (1+1)*(2+1)-1=5 08/01 11:41