#28448: 使用等差(解題思路)


Ist (Ist)

學校 : 不指定學校
編號 : 23295
來源 : [42.77.167.242]
最後登入時間 :
2023-02-18 16:28:05
a215. 明明愛數數 | From: [223.139.208.107] | 發表日期 : 2021-12-11 10:19

假設末項為x

題意:

n + (n + 1) + (n + 2) + ‧‧‧ + (x - 1) + x > m,求項數 = ?

除了n > m且n < 0的情況以外,x 必定大於0(因為負數加負數會越加越小,要一直加到正數才會開始變大)

所以一開始判斷 n > m 就直接輸出 1 項,即可排除 x < 0 的情況

 

依題意列出公式:

((n + x)(x - n + 1)) / 2 > m

nx - n^2 + n + x^2 - nx + x > 2m

x(x + 1) > 2m + n(n - 1)

 

因為x^2 < x(x + 1) < (x + 1)^2

故可得知x^2 < 2m + n(n - 1) < (x + 1)^2

x < √(2m + n(n - 1)) < x + 1,因為 x > 0 ,只取正根

 

x 即為√(2m + n(n - 1))的整數部分

項數 = x - n + 1

 

特殊情況:

((n + x)(x - n + 1)) / 2 = m

x(x + 1) = 2m + n(n - 1)

此狀況下必須再多一項才能符合題意

故項數 = x - n + 2

 
ZeroJudge Forum