一维坐标轴上,蚱蜢一开始在 \(x_0\) 。在第 \(1\) 秒往后的每秒,第 \(i\) 秒蚱蜢可以跳 \(i\) 步。即若当时在 \(x\) ,可以跳到 \(x + i\) 或 \(x - i\) 。额外的,若 \(x\) 为偶数,蚱蜢会往左跳;否则会往右跳。
询问 \(n\) 秒后蚱蜢的坐标。
观察一:初始坐标不重要。
观察二:分奇偶讨论初始坐标。因为 \(x_0 = x_0 + 0\) ,从偏移量 \(0\) 考虑得到 \(g(x)\) 。于是当 \(x_0\) 为偶数,答案为 \(x_0 + g(x)\) 。当 \(x_0\) 为奇数,答案为 \(x_0 - g(x)\) 。
不难发现
\[g(x) = \begin{cases}
0, \quad &x = 0 \\
-1, \quad &x = 1 \\
1, \quad &x = 2 \\
4, \quad &x = 3 \\
0, \quad &x = 4 \\
-5, \quad &x = 5 \\
1, \quad &x = 6 \\
8, \quad &x = 7 \\
0, \quad &x = 8 \\
\cdots
\end{cases} =
\begin{cases}
0, x \equiv 0 (\mod 4) \\
-x, x \equiv 1 (\mod 4) \\
1, x \equiv 2 (\mod 4) \\
1 + x, x \equiv 0 (\mod 4)
\end{cases}
\]
于是有
- \(x_0 \equiv 0 (\mod 2)\) , \(f(n) = x_0 + g(n)\)
- \(x_0 \equiv 1 (\mod 2)\) , \(f(n) = x_0 - g(n)\)
view
#include <bits/stdc++.h>
void solve() {
auto g = [&](long long x) {
if (x % 4 == 0) return 0LL;
else if (x % 4 == 1) return -x;
else if (x % 4 == 2) return 1LL;
else if (x % 4 == 3) return 1LL + x;
};
long long x, n; std::cin >> x >> n;
std::cout << (x & 1 ? x - g(n) : x + g(n)) << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}