AtCoder Beginner Contest 341 D

https://atcoder.jp/contests/abc341/tasks/abc341_d

包除原理＋二分探索です。(first, last]とするとよいです。

// Only one of two
#![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: u64, m: u64) -> u64 {
    if m == 0 {
        n
    }
    else {
        gcd(m, n % m)
    }
}

fn lcm(n: u64, m: u64) -> u64 {
    n / gcd(n, m) * m
}


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

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

// (first, last]
fn bin_search(first: u64, last: u64, N: u64, M: u64, K: u64) -> u64 {
    let L = lcm(N, M);
    let f = |x| {
        x / N + x / M - x / L * 2
    };
    
    let mid = (first + last) / 2;
    if last - first == 1 {
        last
    }
    else if f(mid) >= K {
        bin_search(first, mid, N, M, K)
    }
    else {
        bin_search(mid, last, N, M, K)
    }
}

fn F(N: u64, M: u64, K: u64) -> u64 {
    bin_search(K-1, K*(N+M), N, M, K)
}

fn main() {
    let (N, M, K) = read_input();
    println!("{}", F(N, M, K))
}