CF1487B Cat Cycle 题解
思路分析
在这道题中，很明显是一道数学题，因为有十分明显的数据范围：
\[n \le 10 ^ {9} , k \le 10 ^ {9}
\]
分析如下：
- 对于 \(n\) 为偶数的情况下，猫 \(A\) 和猫 \(B\) 永远不可能相遇，所以直接输出 \(( k - 1 ) \mod n\)。
- 对于 \(n\) 为奇数的情况下，猫 \(A\) 和猫 \(B\) 的相遇周期如下：
\[cycle \gets \frac{n - 1}{2}
\]
猫 \(B\) 多走的路程为 \(\lfloor ( k - 1 ) \div cycle \rfloor\)，最后猫 \(B\) 一共走的路程再对 \(n\) 取模后即为答案，即：
\[ans \gets ( k + \lfloor ( k - 1 ) \div cycle \rfloor - 1 ) \mod n + 1
\]
代码实现
#include <bits/stdc++.h>
using namespace std;
long long t;
long long n, k;
long long cycle;
int main()
{
scanf("%lld", &t);
for (long long i = 1; i <= t; i++)
{
scanf("%lld%lld", &n, &k);
if (n % 2 == 0)
{
printf("%lld\n", (k - 1) % n + 1);
}
else
{
cycle = (n - 1) / 2;
printf("%lld\n", ((k + (k - 1) / cycle) - 1) % n + 1);
}
}
return 0;
}