結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
![]() |
提出日時 | 2021-01-23 14:40:40 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 598 ms / 2,000 ms |
コード長 | 3,005 bytes |
コンパイル時間 | 15,507 ms |
コンパイル使用メモリ | 379,152 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-30 19:24:00 |
合計ジャッジ時間 | 19,658 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
use std::io::{BufRead, Write};// start inputstruct 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 inputfn 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-libraryfn 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_gcdfn 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()));}