https://codeforces.com/contest/1487/problem/B
题目大意
有 $n$ 个格子组成一个环，顺时针依次标号为 $1 \sim n$。猫 $A$ 最初在 $n$ 号格，它每单位时间后逆时针移动一个格，猫 $B$ 最初（$1$ 时刻）在 $1$ 号格，每单位时间后顺时针移动一个格。如果某时刻 $A$ 和 $B$ 移动到同一个格，则 $B$ 继续向前多移动一个格。问 $k$ 时刻后 $B$ 在哪个格。
$2 \le n \le 10^9$。$1 \le k \le 10^9$。
简要题解
注意到如果 $n$ 是偶数则两个猫永远不会相遇在同一格，则直接算 $B$ 即可。
$n$ 为奇数时，注意到 $(n - 1) / 2$ 时刻后会第一次相遇并且 $B$ 会多移动一格，此时两个猫相当于重新处于了 $1$, $n$ 两个格，于是只要按照这个周期计算即可。第一个周期比较奇怪，所以这不是一个纯循环，稍微有点麻烦。
复杂度
$T$：$O(1)$
$S$：$O(1)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
/*
1 5
2 4
4 3
5 2
2 1
3 5
*/
void solve() {
int n, k; cin >> n >> k;
int ans = k;
if (n & 1) {
int m = (n - 1) / 2; // each m step
ans = k / m * (m + 1);
// cerr << n << ' ' << m << ' ' << ans << ' ' << (k % m) << endl;
ans += k % m;
if (k % m == 0) ans--;
}
cout << ((ans - 1) % n + 1) << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. Alice, Bob, Two Teams - Educational Codeforces Round 9