题目:AT_abc290_d
题意
-
有 \(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\)。
思路
-
显然有一个暴力模拟思路,就不多说了,不超时就怪了。
-
首先我们可以发现他是有循环节的,而且不是 ρ 型(从 \(x\) 开始走,走若干步会回到 \(x\))。通过打表可以发现这个循环节长度是固定的,\(len = \frac{n}{\gcd(n,d)}\),且第 \(p\) 个循环节的开头为 \(p - 1\),共有 \(\frac{n}{len}\) 个循环节。所以答案就是 \(\lfloor \frac{k - 1}{len} \rfloor + (k - 1) \% len\)。
-
下面我们可以证明一下为什么循环节为 \(len\),假设 $