ABC 290

D - Marking

方針がなかなか決まらなくて諦めかけたがなんとか自力 AC。

$x_k$ を $k$ 番目に印をつけられるマスの番号とする。 すでに印がつけられていたとしても i の操作で移動したとすると

\begin{align} x_1 &= 0 \nonumber \\ x_2 &= x_1 + D \mod N \nonumber \\ x_3 &= x_2 + D \mod N \nonumber \\ \vdots \nonumber \\ x_k &= x_{k-1} + D \mod N \nonumber \\ \end{align}

これより、$x_k = x_1 + (k-1)D \mod N$ ということがわかる。

操作 ii が初めて起こるのは $\alpha D \equiv 0 \mod N$ となる最小の正の整数 $\alpha$ のときである。すなわち、$\alpha D$ が $N$ の倍数となるような最小の正の整数 $\alpha$ を見つけることができれば周期がわかる。よって操作 ii が何回行われたのかもわかる。

$\alpha D = \mathrm{lcm} (N, D)$ だから $\alpha = D / \mathrm{lcm}(N, D)$

これらより $k$ 番目に印がつけられるマスは $\lfloor \frac{k-1}{\alpha} \rfloor$ 回 操作 ii を実行したあと $k-1 \mod \alpha$ 回 操作 i をしたときのマスであるから

$x_k = \lfloor \frac{k-1}{\alpha} \rfloor + (k-1 \mod \alpha) D \mod N$ である。

※ $n\alpha D \equiv 0 \mod N~ (n \in \mathbb{Z})$ なので $x_k = \lfloor \frac{k-1}{\alpha} \rfloor + (k-1) D \mod N$ としても結果は同じ。

void solve() {
    int T;
    cin >> T;
    rep(i, T) {
        ll n, d, k;
        cin >> n >> d >> k;

        // ll g = gcd(n, d);
        // ll a = n / g;
        ll a = lcm(n, d) / d;

        cout << ((k - 1) / a + ((k - 1) % a) * d) % n << endl;
    }
}