結果

問題 No.1358 [Zelkova 2nd Tune *] 語るなら枚数を...
ユーザー StrorkisStrorkis
提出日時 2021-01-23 14:40:40
言語 Rust
(1.77.0)
結果
AC  
実行時間 531 ms / 2,000 ms
コード長 3,005 bytes
コンパイル時間 2,250 ms
コンパイル使用メモリ 150,740 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-29 01:35:29
合計ジャッジ時間 5,408 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 4 ms
4,376 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 4 ms
4,376 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 472 ms
4,380 KB
testcase_12 AC 413 ms
4,380 KB
testcase_13 AC 531 ms
4,376 KB
testcase_14 AC 371 ms
4,376 KB
testcase_15 AC 410 ms
4,376 KB
testcase_16 AC 365 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::{BufRead, Write};

// start input
struct Lines<B> { b: B, buf: Vec<u8> }
 
impl<B: BufRead> Lines<B> {
    fn next(&mut self) -> &str {
        self.buf.clear();
        self.b.read_until(b'\n', &mut self.buf).ok();
        if self.buf.ends_with(&[b'\n']) {
            self.buf.pop();
            if self.buf.ends_with(&[b'\r']) {
                self.buf.pop();
            }
        }
        std::str::from_utf8(&self.buf).unwrap()
    }
}

macro_rules! parse {
    ($s:expr, Usize1) => (parse!($s, usize) - 1);
    ($s:expr, Bytes) => ($s.as_bytes().to_vec());
    ($s:expr, Chars) => ($s.chars().collect::<Vec<_>>());
    ($s:expr, $t:ty) => ($s.parse::<$t>().unwrap());
}

macro_rules! scan {
    ($iter:expr, ($($t:ident),*)) => (
        ($(scan!($iter, $t)),*)
    );
    ($iter:expr, [$t:ident]) => (
        $iter.map(|s| parse!(s, $t)).collect::<Vec<_>>()
    );
    ($iter:expr, $t:ident) => (
        parse!($iter.next().unwrap(), $t)
    );
}

macro_rules! read {
    ($lines:expr, [$t:tt; $n:expr]) => (
        (0..$n).map(|_| read!($lines, $t)).collect::<Vec<_>>()
    );
    ($lines:expr, $t:tt) => ({
        let iter = &mut $lines.next().split(' ');
        scan!(iter, $t)
    });
}
// end input

fn gcd(mut a: i64, mut b: i64) -> i64 {
    while b > 0 {
        let r = a % b;
        a = b;
        b = r;
    }
    a
}

// start inv_gcd
// reference: https://github.com/atcoder/ac-library
fn safe_mod(mut x: i64, m: i64) -> i64 {
    x %= m;
    if x < 0 { x + m } else { x }
}

fn inv_gcd(a: i64, b: i64) -> (i64, i64) {
    let a = safe_mod(a, b);
    if a == 0 { return (b, 0); }

    let (mut s, mut t) = (b, a);
    let (mut m0, mut m1) = (0, 1);

    while t != 0 {
        let u = s / t;
        s -= t * u;
        m0 -= m1 * u;

        std::mem::swap(&mut s, &mut t);
        std::mem::swap(&mut m0, &mut m1);
    }

    (s, if m0 < 0 { m0 + b / s } else { m0 })
}
// end inv_gcd

fn run<B: BufRead, W: Write>(mut lines: Lines<B>, mut writer: W) {
    const MOD: i64 = 1_000_000_007;

    for _ in 0..read!(lines, usize) {
        let (mut n, mut k, mut h, y) = {
            read!(lines, (i64, i64, i64, i64))
        };

        if n > k {
            std::mem::swap(&mut n, &mut k);
        }
        if k > h {
            std::mem::swap(&mut k, &mut h);
        }

        let mut ans = 0;
        let g = gcd(n, k);
        let (a, b) = (n / g, k / g);
        let p = inv_gcd(a, b).1;
        let q = (1 - p * a) / b;
        for y in (0..=y).rev().step_by(h as usize).filter(|y| y % g == 0) {
            let x = y / g;
            let upper = if q < 0 { x * q - (a - 1) } else { x * q } / a;
            let lower = (-x * p) / b;
            ans += upper - lower + 1;
            ans %= MOD;
        }
        writeln!(writer, "{}", ans).ok();
    }
}

fn main() {
    let (stdin, stdout) = (std::io::stdin(), std::io::stdout());
    let lines = Lines { b: stdin.lock(), buf: Vec::new() };
    run(lines, std::io::BufWriter::new(stdout.lock()));
}
0