梅莉的市场经济学

思路

使用二分找到该数处在哪个完整周期中，然后通过确定该周期的区间l, r，可以找到该数的答案

推导

首先我们需要找到每个周期开始位置的关系，如2 7 19 ....
一看上去没什么规律，看他们的差值可以发现其实是个一个等差数列1 5 9 ....
那么可以通过等差数列求和来确定每个周期的开始位置，求和公式为:na1 + n(n-1)d / 2,得到2n(n-1)+n，然后向后挪一格即为开始位置的坐标
也就是2n(n-1)+n+1，继而可以求出结束位置为2n(n-1)+n+1+4n

void solve() {
	LL n;
	cin >> n;
	if (n == 1) {
		cout << 0 << endl;
		return ;
	}
	LL l = 1, r = 2e9, a = 0, mid;
	while (l < r) {
		mid = (l + r) >> 1;
		LL x = 2 * mid * mid - mid + 1;
		LL y = 2 * mid * mid + 3 * mid + 1;
		if (x <= n && y >= n) {
			a = mid;
			break;
		}
		if (x > n) r = mid;
		else l = mid + 1;
	}
	l = 2 * a * a - a + 1;
	if (n <= l + a) {
		cout << n - l << endl;
	}else if (n <= l + 3 * a) {
		cout << 2 * a - n + l << endl;
	}else cout << n - l - 4 * a << endl;
}