D. 标记

思路：找到第K次标记的方块编号，标记过程从0开始，每次尝试标记位置，互质时，标记的顺序会覆盖所有方块，而且每个位置只被标记一次。如果不互质，求两个数的最大公约数。

#include<bits/stdc++.h>
using namespace std;
long long t,n,d,k,g,c,p;
long long gcd(long long x, long long y){
    while(y!=0){
        long long a=y;
        y=x%y;
        x=a;
    }
    return x;
}
int main(){
	freopen("D.in","r",stdin);
	freopen("D.out","w",stdout);
    cin>>t;
    for(long long i=1;i<=t;i++){
        cin>>n>>d>>k;
        k--;
        g=gcd(d,n);
        c=k/(n/g);
        p=(k%(n/g)*d)%n;
        cout<<p+c<<endl;  	
	}
    return 0;
}