作者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/cn.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