题目
Klee有一个数组a长度n包含整数[K,K+1,...K+n]按此顺序。Klee想要选择一个索引i（1<=i<=n）,使得x=|a1+a2+...+ai-ai+1-...-an|最小化。请注意，对于任意整数z，|z|表示x.
输出x.
输入
第一行包含 t( 1≤t≤1e4） — 测试用例的数量。每个测试用例包含两个整数 n和 k( 2≤n,k≤109） — 数组的长度和数组的起始元素。
输出
对于每个测试用例，输出最小值 x在新行上。
例子
输入
4
2 2
7 2
5 3
1000000000 1000000000
输出
1
5
1
347369930
代码示例
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
long long t;
cin >> t;
while(t--)
{
long long n, k;
cin >> n >> k;
long long l = 1, r = n + 1, s1, s2, sum = n * (2 * k + n - 1) / 2;
while(l < r)
{
long long mid = l + r + 1 >> 1;
s1 = (2 * k + mid - 1) * mid / 2;
s2 = sum - s1;
if(s1 <= s2) l = mid;
else r = mid - 1;
}
long long left = ((2 * k + l - 1) * l) / 2, right = sum - left;
long long le = ((2 * k + l) * (l + 1)) / 2, ri = sum - le;
cout << min(abs(left - right), abs(le - ri)) << endl;
}
}