結果

問題 No.2526 Kth Not-divisible Number
コンテスト
ユーザー tttttaaa
提出日時 2023-11-03 21:47:18
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 261 ms / 2,000 ms
コード長 2,996 bytes
コンパイル時間 13,354 ms
コンパイル使用メモリ 378,976 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-25 19:55:42
合計ジャッジ時間 16,355 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unnecessary parentheses around `while` condition
  --> src/main.rs:42:11
   |
42 |     while (l + 1 < r) {
   |           ^         ^
   |
   = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
   |
42 -     while (l + 1 < r) {
42 +     while l + 1 < r {
   |

ソースコード

diff # 

#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(non_snake_case)]

pub use __cargo_equip::prelude::*;

use kyopro_io::get;
use std::io::{StdoutLock, Write};

const JU_5: usize = 100_000;
const JU_9: usize = JU_5 * 10_000;
const JU_18: usize = JU_9 * JU_9;
const INF: usize = JU_9 + 100_100;
const INFL: usize = JU_18 * 2;

const MULTIPLE_TEST_CASE: bool = true;

fn gcd(a: usize, b: usize) -> usize {
    if a > b {
        return gcd(b, a);
    }
    if a == 0 {
        return b;
    }
    gcd(b % a, a)
}
fn lcm(a: usize, b: usize) -> usize {
    let g = gcd(a, b);
    (a / g) * (b / g) * g
}

fn _main(writer: &mut std::io::BufWriter<StdoutLock>) {
    let (a, b, k) = get!(usize, usize, usize);
    let L = lcm(a, b);
    let mut l = 0;
    let mut r = INFL*2;
    let _f = |m: usize| {
        let x = m / a + m / b - m / L;
        return (m - x) < k;
    };
    while (l + 1 < r) {
        let m = (l + r) / 2;
        if _f(m) {
            l = m;
        } else {
            r = m;
        }
    }
    writeln!(writer, "{}", r).unwrap();
}
// writeln!(writer, "{}", ans).unwrap();

fn main() {
    let t = if MULTIPLE_TEST_CASE { get!(usize) } else { 1 };

    let stdout = std::io::stdout();
    let mut writer = std::io::BufWriter::new(stdout.lock());

    for _ in 0..t {
        _main(&mut writer);
    }
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `kyopro-io 0.1.0 (path+████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::kyopro_io`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod kyopro_io {pub use crate::__cargo_equip::macros::kyopro_io::*;#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_io_get{($t:ty)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();line.trim().parse::<$t>().unwrap()}};($($t:ty),*)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();let mut iter=line.split_whitespace();($(iter.next().unwrap().parse::<$t>().unwrap(),)*)}};($t:ty;$n:expr)=>{(0..$n).map(|_|get!($t)).collect::<Vec<_>>()};($($t:ty),*;$n:expr)=>{(0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()};($t:ty;;)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()}};($t:ty;;$n:expr)=>{(0..$n).map(|_|get!($t;;)).collect::<Vec<_>>()};}macro_rules!get{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_io_get!{$($tt)*})}}
    }

    pub(crate) mod macros {
        pub mod kyopro_io {pub use crate::__cargo_equip_macro_def_kyopro_io_get as get;}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod kyopro_io {}
    }
}
0