ZeroJudge 解題筆記：f885. 加總

作者：王一哲
日期：2025年10月28日


ZeroJudge 題目連結：f885. 加總

解題想法

這題考數學，要先推導公式。首先用等差級數公式 $$ \frac{(n+a)(n-a+1)}{2} \geq x ~\Rightarrow~ n^2 + n - a^2 + a - 2x \geq 0 $$ 用公式解 $$ n = \frac{-1 \pm \sqrt{1^2 - 4 \times (-a^2 + a - 2x)}}{2} = \frac{-1 \pm \sqrt{4a^2 - 4a + 8x + 1}}{2} $$ 從範例測資來看，答案應該是正整數，因此上式的解要取正值，如果計算結果不是正整數，則用 math.ceil 向上取最接近的正整數。

Python 程式碼

這題有卡 I/O，如果每次計算完之後就用 print 印出答案，在最後一筆測資會超時。改用 sys.stdion.readlines() 一次讀取所有測資，再將所有的計算結果全部存進串列之中，最後再用 sys.stdout.write 及 join 合併要輸出的答案，盡量縮短運算時間。使用時間約為 0.3 s，記憶體約為 15.7 MB，通過測試。

import sys, math

lines = sys.stdin.readlines()
t = int(lines[0])
ans = []
for line in lines[1:]:
    a, x = map(int, line.split())
    ans.append(str(math.ceil((-1 + math.sqrt(4*(a**2) - 4*a + 8*x + 1))/2)) + "\n")
sys.stdout.write("".join(ans))

C++ 程式碼

使用時間約為 32 ms，記憶體約為 136 kB，通過測試。

#include <cstdio>
#include <cmath>
typedef unsigned long long LL;
using namespace std;

int main() {
    LL t, a, x; scanf("%llu", &t);
    while(t--) {
        scanf("%llu %llu", &a, &x);
        printf("%llu\n", LL(ceil((-1.0 + sqrt(4*a*a - 4*a + 8*x + 1))/2.0)));
    }
    return 0;
}