f885 - 加總
題目描述
題目給定兩個整數 a 和 x，要求找到最小的整數 n，使得從 a 到 n 的所有整數之和大於或等於 x。
解題思路
這題可以利用等差數列的求和公式來加速計算。從 a 到 n 的和可以表示為 (n + 1) * n / 2 - (a - 1) * a / 2。題目要求找到最小的 n 滿足這個和大於等於 x。
由於和是關於 n 的單調遞增函數，因此可以使用二分搜尋法來找到最小的 n。二分搜尋的範圍是從 a 到 x。在每次二分搜尋中，計算從 a 到當前 n 的和，如果和大於等於 x，則更新 n 的上限，否則更新 n 的下限。
複雜度分析
- 時間複雜度: O(T * log(x))，其中 T 是測試案例的數量，x 是輸入的 x 值。二分搜尋的複雜度是 O(log(x))，而題目有多組測試案例，因此總時間複雜度是 O(T * log(x))。
- 空間複雜度: O(1)，因為程式碼只使用了常數級別的額外空間。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
long long int a,x,t,lsum;
inline long long int read(){
long long int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(long long int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[21],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
long long int bs(long long int l,long long int r){
if(l>r)return l;
long long int m=(l+r)/2,sum=(m+1)*m/2-lsum;
return (sum>=x)?bs(l,m-1):bs(m+1,r);
}
int main(){
t=read();
while(t--){
a=read();
x=read();
lsum=(a-1)*a/2;
write(bs(a,x));
putchar_unlocked('\n');
}
}