n 要表為連續整數
可以假設可以是連續 1, 2 ... d 個連續整數
假設 x, y 為左右邊界
x = y - d + 1 (d 為連續個數)
--> (y + x) * (y - x + 1) / 2 = n (梯形公式)
--> (y + y - d + 1) * (y - y + d - 1 + 1) = 2n
--> (2y - d + 1) * (d) = 2n
--> 2y - d + 1 = 2n/d
此時假設 2n 可以整除 d 才有解
以 n = 15 為例, 對 30 分解得 [1, 2, 3, 5, 6, 10, 15, 30]
d = 1 : 2y - d + 1 = 30, 2y = 30, y = 15, x = 15 (n 為任意數, 一定有有此解)
d = 2 : 2y - d + 1 = 15, 2y = 15, y = 8, x = 7 (n 為奇數, 一定有有此解)
d = 3 : 2y - d + 1 = 10, 2y = 12, y = 6, x = 4
d = 5 : 2y - d + 1 = 6, 2y = 10, y = 5, x = 1 ( 正解 )
d = 6 : 2y - d + 1 = 5, 2y = 10, y = 5, x = 0 ( x < 1 時, 可以 break )
以 n = 10 為例, 對 20 分解得 [1, 2, 4, 5, 10, 20]
d = 1 : 2y - d + 1 = 20, 2y = 20, y = 10, x = 10 (n 為任意數, 一定有有此解)
d = 2 : 2y - d + 1 = 10, 2y = 9 (y 非整數 pass)
d = 4 : 2y - d + 1 = 5, 2y = 8, y = 4, x = 1 ( 正解 )
d = 5 : 2y - d + 1 = 4, 2y = 8, y = 4, x = 0 ( x < 1 時, 可以 break )
快速的因數分解很重要,可以節省跑很多迴圈。
別再抱怨 python 怪怪的,別只用蠻力。
1125986325895202 = 1184179952 + ... + 1185130427