切換
舊版
前往
大廳
主題

ZeroJudge - a471: givesum~連續整數的固定和 解題心得

Not In My Back Yard | 2019-01-14 23:00:06 | 巴幣 0 | 人氣 256

題目連結:


題目大意:
又一題跟這題類似的,但是這次是給定一正整數 n (n ≦ 100, 000, 000),並求出所有連續正整數區間之和為 n 的方法。

若存在這樣的方法,就將方法全數輸出,並按照輸出格式;反之,輸出「No Solution...」。並在輸出完之後空一列空行。



範例輸入:
27
16
12


範例輸出:
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 值。(此為代入兩種關係式的簡化版)

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作