AtCoder Beginner Contest 290 D

https://atcoder.jp/contests/abc290/tasks/abc290_d

例えば、N=10、D=4なら、0 -> 4 -> 8 -> 2 -> 6 -> 0だから、周期が5になります。
Kが5より大きければ1つずれます。

// Marking
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn gcd(n: i64, m: i64) -> i64 {
    if m == 0 {
        n
    }
    else {
        gcd(m, n % m)
    }
}

//////////////////// process ////////////////////

fn read_input() -> (i64, i64, i64) {
    let v = read_vec();
    let N = v[0];
    let D = v[1];
    let K = v[2];
    (N, D, K)
}

fn f(N: i64, D: i64, K: i64) -> i64 {
    let d = gcd(N, D);
    let P = N / d;  // period
    let r = (K - 1) % P;
    let q = (K - 1) / P;
    q + r * D % N
}

fn main() {
    let T: usize = read();
    for _ in 0..T {
        let (N, D, K) = read_input();
        println!("{}", f(N, D, K))
    }
}