#20592: python 快速解法


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [114.42.180.252]
最後登入時間 :
2024-05-17 15:04:41
e626. 11254 - Consecutive Integers -- UVA | From: [61.223.42.3] | 發表日期 : 2020-02-11 12:56

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 怪怪的,別只用蠻力。

 
#20593: Re:python 快速解法


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [114.42.180.252]
最後登入時間 :
2024-05-17 15:04:41
e626. 11254 - Consecutive Integers -- UVA | From: [61.223.42.3] | 發表日期 : 2020-02-11 13:10

1125986325895202 = 1184179952 + ... + 1185130427

 
 
ZeroJudge Forum