市场每一天的贸易差可以视为一个有周期性规律的数列 a:[0],[0,1,0,−1,0],[0,1,2,1,0,−1,−2,−1,0],[0,1,2,3,2,1,0,−1,−2,−3,−2,−1,0]…
具体而言,a 可以被分为无穷段,第 i 段的内容为 0,1,…,i,i−1,…,0,−1,…,−i,−i+1,…,0。如下图所示,是将 a 数列内的前一些点绘制在坐标轴上的情况:
每段都是一个类似正弦函数的波形, 将每段的左端点和右端点的坐标差叫做段的长度
由图中易得, 第n
段的长度$LEN(n) = 4 n - 4$, 第n
段的右边界为$R(n) = n + \sum^n_{i=1}LEN(i) = 2n^2 - n$
二分查找x所在的段数, 随后根据位置分类讨论获得答案。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll R(ll n) {return 2ll * n * n - n;}
ll get(ll x) {
ll l = 1, r = 2e9;
while (l < r) {
ll mid = (l + r) / 2ll;
if (x <= R(mid)) r = mid;
else l = mid + 1;
}
ll n = l;
r = R(n), l = r - (4ll * n - 4ll);
if (x <= l + n - 1ll) return x - l;
else if (x <= r - n + 1) return l + 2ll * n - 2ll - x;
return x - r;
}
int main () {
int m; cin >> m;
while (m -- ) {
ll x; cin >> x;
cout << get(x) << endl;
}
}