題目連結:
又一題跟
這題類似的,但是這次是給定一正整數 n (n ≦ 100, 000, 000),並求出
所有連續正整數區間之和為 n 的方法。
若存在這樣的方法,就將方法全數輸出,並按照輸出格式;反之,輸出「No Solution...」。並在輸出完之後空一列空行。
2-7
8-10
13-14
No Solution...
3-5
一如往常地,我們將正整數 n 的奇因數全部找出來。而因為我們要求區間 a-b ,所以滿足以下關係式(其中 f 為 n 的某一奇因數):
或
上圖的部分是 a 、 b 一奇一偶,下圖則是 a 、 b 的奇偶性相同。
不管如何, b 的值都不會變,都會是
確定了 b 值之後,上面兩種關係式都各將 b 代入進去。因為只會有一式成立, a 的值也就確認了。(※註一)
所有的奇因數都代進去,求出所以區間之後,對其左端點(也就是 a )排序。再輸出即是題目所求。而沒有任何解的時候, n 值必為 2 的冪次,此時輸出「No Solution...」。
※註一:將 a 設為 f - b 。如果 a 為正,即是所求;反之, -a + 1 才是我們要的 a 值。(此為代入兩種關係式的簡化版)
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。