この問題を解くには、まず以下の事実を知っている (あるいは実験などで見つける) 必要があります。

\(A,B\) を正整数とし、\(A\) と \(B\) の最大公約数を \(g\) とおく。\(A=ag,B=bg\) と表されるとき、\(a\) 個の数 \(0,B \bmod A,2B \bmod A,\dots,(a-1)B\bmod A\) の中には、\(0,g,2g,\dots,(a-1)g\) (すなわち \(0\) 以上 \(A\) 未満の \(g\) の倍数) がちょうど \(1\) 回ずつ現れる。

例えば \(A=12,B=9\) のとき、\(g=3,a=4,b=3\) です。このとき、\(0,B\bmod A,2B\bmod A, 3B\bmod A\) の値はそれぞれ \(0,9,6,3\) ですから、\(0\) 以上 \(A\) 未満の \(g\) の倍数がちょうど \(1\) 回ずつ現れています。

この事実を用いて元の問題を解いていきましょう。以下、\(N\) と \(D\) の最大公約数を \(g\) とおき、\(N=gn,D=gd\) とします。

\(0,D \bmod N,2D \bmod N,\dots,(n-1)D\bmod N\) が全て異なることから、\(i\ (1\leq i \leq n)\) 番目に印をつけるマスは \((i-1)D\bmod N\) です。

\(n <N\) すなわち \(g\geq2\) のととき、 \(n+1\) 番目に印をつけるマスを考えましょう。はじめ \(x\) は \(nD\bmod N\) で初期化されますが、\(nD = gnd=Nd\) より \(x=0\) であるため、既に印が付いています。したがって \(x=1\) と更新されますが、\(g\geq2\) よりマス \(1\) にはまだ印がついていないので、\(n+1\) 番目に印をつけるのはマス \(1\) になります。その後は、先ほどと同様 \(1,1+(D \bmod N),1+(2D \bmod N),\dots,1+((n-1)D\bmod N)\) に順に印をつけた後、\(x=1\) と初期化されるので \(x=2\) と更新し… と続いていきます。まとめると、

• \(i\ (1\leq i \leq n)\) 番目に印をつけるマスは \((i-1)D\bmod N\) であり、これによって \(g\) の倍数のマス全てに印がつく。
• \(n+i\ (1\leq i \leq n)\) 番目に印をつけるマスは \(1+((i-1)D\bmod N)\) であり、これによって \(g\) で割ると \(1\) 余るマス全てに印がつく。
• \(2n+i\ (1\leq i \leq n)\) 番目に印をつけるマスは \(2+((i-1)D\bmod N)\) であり、これによって \(g\) で割ると \(2\) 余るマス全てに印がつく。
• (以下同様)

というように操作が進んでいきます。よって、\(K\) 番目に印をつけるマスは \(\lfloor \frac{K-1}{n} \rfloor + ((K-1)D \bmod N)\) と計算できます。

想定解 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, d, k;
        cin >> n >> d >> k;
        --k;
        int a = n / gcd(n, d);
        cout << (long long) d * k % n + k / a << '\n';
    }
}