AT_abc290_d
题目：AT_abc290_d
链接：洛谷，AT，逐月
题意
-
有 \(n\) 个格子，编号为 \(0 \sim n - 1\)，围成一个圈，按以下方式标记格子（直到所有格子均被标记）：
- 标记 \(0\)。
- 令 \(x\) 为上一次标记的格子，\(y = (x + d) \% n\)。
- 以此美剧 \(y, y + 1, \cdots\) 直到找到一个没被标记过的格子 \(z\)，标记 \(z\)。
-
请输出第 \(k\) 个被标记的格子，给定 \(T\) 组数据。、
-
数据范围：\(1 \le t \le 10^5, 1 \le n, d, k \le 10^9, k \le n\)。
思路
-
显然有一个暴力模拟思路，就不多说了，不超时就怪了。
-
可以先把 \(d \%= n\) 首先我们可以发现他是有循环节的，而且不是 ρ 型（从 \(x\) 开始走，走若干步会回到 \(x\)）。通过打表可以发现这个循环节长度是固定的，\(len = \frac{n}{\gcd(n,d)}\)，且第 \(p\) 个循环节的开头为 \(p - 1\)，共有 \(\frac{n}{len}\) 个循环节。所以答案就是 \(\lfloor \frac{k - 1}{len} \rfloor + (k - 1) \% len\)。（打表找规律）
-
下面我们可以证明一下为什么循环节为 \(len\)，假设从 \(0\) 开始走，走 \(s\) 步走了 \(t\) 圈，有 \(sd = tn\)，$ s \cdot \frac{d}{\gcd(n,d)} = t \cdot \frac{n}{\gcd(n,d)}$，那么最小一组解为 \(\begin{cases} s = \frac{n}{\gcd(n,d)} \\ t = \frac{d}{\gcd(n,d)} \end{cases}\)，而 \(len = s\)，结合打表也可通过此题。（不完整证明）。
-
但是