切換
舊版
前往
大廳
主題

ZeroJudge - e626: 11254 - Consecutive Integers　解題心得

Not In My Back Yard | 2020-02-01 02:05:01 | 巴幣 0 | 人氣 218
題目連結：
題目大意：
輸入有多列，每列給定一正整數 n （n ≦ 10 ^ 9，n ＝ -1 時代表輸入結束）。請找到連續正整數數列，其總和為 n 。如果有多組數列，請輸出含有最多數字的（數列最長的）那一組。

例如 n ＝ 15 ，則有 1 + ...  + 5 、4 + ... + 6 、 7 + ... + 8 、 15 + ... + 15 這四種。（輸出格式即是前面列舉的形式）數字最多的是第一種，因此所求為 1 + ...  + 5 。

範例輸入：
8
15
35
-1
範例輸出：
8 = 8 + ... + 8
15 = 1 + ... + 5
35 = 2 + ... + 8
解題思維：
假設連續正整數的上界、下界分別為 X 、 Y ，則 n ＝ Y + ... + X 。

改寫上式可以變成
（X － Y ＋ 1）×（X ＋ Y）＝ 2n
並假設 a ＝ X － Y ＋ 1 、 b ＝ X ＋ Y ，此題於是變成了找 2n 的因數。而原本的 X ＝ （b ＋ a － 1） ÷ 2 、 Y ＝ （b －  a ＋ 1） ÷ 2 。

而為了要找到有最多數字的數列 Y + ... + X ，因此要最大化 X － Y ＋ 1 的值。根據上面的假設，此即為 a 。

而觀察原式（X － Y ＋ 1）×（X ＋ Y）可以發現 a 、b 兩者必定一奇一偶且 b ＞ a 。因此可以用這些條件來找到 a ：
首先令 a ＝ √(2n) 取整數，從此開始找起。令 b ＝ 2n ÷ a （一樣取整數）。如果 a × b ≠ 2n ，則將 a 往下修（將 a 減去 1）；如果 a 、 b 的奇偶性相同，則同樣也將 a 往下修。

當找到a 、 b 滿足 a × b ＝ 2n 且兩者一奇一偶時，此時的 a 即是最大的可能值。代回原式即可得出原本的 X 、 Y ，此即所求。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#數論
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

相關創作

鳥鳥玩數學-有趣的擲骰子機率問題(2022 大阪大學前期)
0 201
鳥鳥玩數學-高斯符號找質因數個數及原理(2020-2021 Hồ Chí Minh，Vietnam)
1 304
鳥鳥玩數學-平方差整數解之小技巧
1 279
鳥鳥玩數學-2022年考生要注意的事
0 344
鳥鳥玩數學-分母為相異質數不定方程(2016 越南數學選拔)
1 261
鳥鳥玩數學-對數與數論結合方程組問題(2019 AIME I)
0 331
鳥鳥玩數學-1000! 1000!! 999!! 找質因數個數(2018大阪市立大學)
0 215
鳥鳥玩數學-經典數論名題133^5+110^5+84^5+27^5=n^5 (1989 AIME)
0 298
鳥鳥玩數學-解 2^x+2^y+2^z=2336 (1982 Vietnam Mathematical Olympic)
0 231
鳥鳥玩數學-數論與平面座標的結合(2020 北海道大學 前期)
0 173
鳥鳥玩數學 三角函數與對數的結合(2019 京都大學前期)
0 263
鳥鳥玩數學-為兩年後準備，sqrt(a)+sqrt(b)=2023 正整數解
1 319
鳥玩數學-與2015互質，第2015個數(104高雄市聯招)
0 220
鳥鳥玩數學-證明sin1 cos1 tan1為無理數
0 305
鳥鳥玩數學-餘弦定理意想不到的用法，質數與餘弦定理的組合
0 277
鳥鳥玩數學-什麼!! n個相異自然數和等於n個相異自然數積只有一組解(1977 岐阜大學)
0 175
達人 《憂國的莫里亞蒂》中的數學公式
68 3197
cf #460 (Div. 2) pE Congruence Equation
0 145

更多創作

追蹤 創作集
其他創作
作品資料夾