題目在 https://zerojudge.tw/ShowProblem?problemid=f885
這題我想的太複雜了. 測資#8 #9 #10沒過, 我猜測是a或是x可能是負數. 所以寫了一段針對負數的判斷, 可是錯誤依然不動如山. 後來才想到是可能a累加後會太大超出int的範圍. 直接改用long long就一次通過.
題目要求的是 滿足 (a+n)*(n-(a-1))/2 >= x的n.
化簡後就是求n 滿足 n(n+1)>=2x+a(a-1)
由於x,a已知, 而且我們知道 n <= sqrt(2x+a(a-1)) <= n+1
所以n = int(sqrt(2x+a(a-1))) 後算算n(n+1) 是不是大於x, 不是的話答案就是n+1.
完整程式如下, 處理a,x為負數的部分我沒拿掉.
#include <stdio.h>
#include <math.h>
#include <cmath>
#include <iostream>
int main(){
int all;
scanf("%d",&all);
while(all-->0){
long long a,x;
scanf("%lld %lld",&a, &x);
//處理當a,x小於0
if(a<0){
if(x<=0){
if(a==x){
printf("%lld\n",-a-1);
continue;
}else{
printf("%lld\n",-a);
continue;
}
}else{
a=-a+1;
if(x<=a){
printf("%lld\n",a);
continue;
}
}
}
long long target = 2*x+a*(a-1);
long long n=sqrtl(target);
if(n*(n+1)<target){
printf("%lld\n",n+1);
}else{
printf("%lld\n",n);
}
}
scanf("%c %c",&all,&all);
}
