ABC290D数学周期GCD计数

#include <stdio.h>
int T, n, m, i, j, k, a, c;
int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a%b);
}
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &n, &a, &k);
        k--, c = gcd(n, a);//增加k次a
        printf("%lld\n", (1ll*a*k+k/(n/c))%n);
    }//互质不用加1，否则每n/c次加1，共加k/它次
    return 0;
}