#413232 (Rust) No.187 中華風 (Hard)

• 問題: No.187 中華風 (Hard)
• ユーザー: Kohei Asano
• 提出日時: 2020-01-01 18:28:47
• 言語: Rust (1.77.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 4,573 bytes
• コンパイル時間: 13,202 ms
• コンパイル使用メモリ: 378,256 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-22 13:23:29
• 合計ジャッジ時間: 15,971 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	AC	143 ms; 5,248 KB
testcase_05	AC	143 ms; 5,248 KB
testcase_06	AC	143 ms; 5,248 KB
testcase_07	AC	143 ms; 5,248 KB
testcase_08	AC	95 ms; 5,248 KB
testcase_09	AC	95 ms; 5,248 KB
testcase_10	AC	92 ms; 5,248 KB
testcase_11	AC	144 ms; 5,248 KB
testcase_12	AC	143 ms; 5,248 KB
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	109 ms; 5,248 KB
testcase_16	AC	111 ms; 5,248 KB
testcase_17	AC	1 ms; 5,248 KB
testcase_18	AC	1 ms; 5,248 KB
testcase_19	AC	1 ms; 5,248 KB
testcase_20	AC	109 ms; 5,248 KB
testcase_21	AC	1 ms; 5,248 KB
testcase_22	AC	143 ms; 5,248 KB
testcase_23	AC	1 ms; 5,248 KB
testcase_24	AC	1 ms; 5,248 KB

コンパイルメッセージ

warning: unused imports: `max`, `min`
 --> src/main.rs:2:16
  |
2 | use std::cmp::{max, min};
  |                ^^^  ^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused imports: `HashMap`, `HashSet`
 --> src/main.rs:3:24
  |
3 | use std::collections::{HashMap, HashSet};
  |                        ^^^^^^^  ^^^^^^^

warning: variable does not need to be mutable
   --> src/main.rs:157:9
    |
157 |     let mut ans = garner(&mut mr, MOD);
    |         ----^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

ソースコード

// =========
use std::cmp::{max, min};
use std::collections::{HashMap, HashSet};
use std::process::exit;

const MOD: i64 = 1000000007;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    // var... 変数の識別子, $t...型を一つよむ
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        //ここで繰り返し
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    //
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    // 配列の最後のNestではここで型が指定されてparseされる
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// =========

// mod mの体におけるaの逆元
macro_rules! impl_modinv {
    ($U:ty) => {
        fn mod_inv(a: $U, m: $U) -> $U {
            let mut ab = (a as i64, m as i64);
            let mut uv = (1, 0);
            let mut t: i64;
            while ab.1 != 0 {
                t = ab.0 / ab.1;
                ab = (ab.1, ab.0 - t * ab.1);
                uv = (uv.1, uv.0 - t * uv.1);
            }
            // if ab.0 != 1 {
            //     // panic!("{} and {} are not coprime g={}", a, m, ab.0);
            //     println!("{:?}", -1);
            //     exit(0);
            // }
            let inv = uv.0 % m as i64;
            if inv < 0 {
                (inv + m as i64) as $U
            } else {
                inv as $U
            }
        }
    };
}
fn gcd(a: i64, b: i64) -> i64 {
    let (a, b) = if a < b { (b, a) } else { (a, b) };
    if b == 0 {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

impl_modinv!(i64);
// mr[i].0 ... 互いに素
fn garner(mr: &mut Vec<(i64, i64)>, m: i64) -> i64 {
    mr.push((m, 0));
    // coef... mixed radixの係数, constants... 前まで求めた係数
    let mut coef: Vec<i64> = vec![1; mr.len()];
    let mut constants: Vec<i64> = vec![0; mr.len()];
    for i in 0..mr.len() - 1 {
        let mut v: i64 = (mr[i].1 - constants[i]) * mod_inv(coef[i], mr[i].0) % mr[i].0;
        if v < 0 {
            v += mr[i].0;
        }
        for j in i + 1..mr.len() {
            constants[j] += coef[j] * v;
            constants[j] %= mr[j].0;
            coef[j] *= mr[i].0;
            coef[j] %= mr[j].0;
        }
    }
    constants[mr.len() - 1]
}

fn main() {
    input! {
        n: usize,
        mr: [(i64,i64);n]
    }
    let mut mr = mr.iter().map(|e| (e.1, e.0)).collect::<Vec<(i64, i64)>>();
    // 前処理 m を互いに素にする
    let mut lcm = false;
    for i in 0..mr.len() {
        for j in i + 1..mr.len() {
            if mr[i].1 == 0 {
                lcm = true;
            }
            let mut g = gcd(mr[i].0, mr[j].0);
            // 解の条件チェック
            if (mr[i].1 - mr[j].1) % g != 0 {
                println!("{:?}", -1);
                exit(0);
            }
            //ひとまず互いに素にする
            mr[i].0 /= g;
            mr[j].0 /= g;

            //gi...mr[j].0に残らないやつ(とりきってない)
            let mut gi = gcd(mr[i].0, g);
            //mr[j]に残るのは必ず含まれるけど不純
            let mut gj = g / gi;
            // giが取り切れなかったのをとっていく
            while g != 1 {
                g = gcd(gi, gj);
                gi *= g;
                gj /= g;
            }
            mr[i].0 *= gi;
            mr[j].0 *= gj;
            // あまりの更新
            mr[i].1 %= mr[i].0;
            mr[j].1 %= mr[j].0;
        }
    }
    let m: i64 = mr.iter().fold(1, |res, e| res * e.0 % MOD);
    let mut ans = garner(&mut mr, MOD);
    if lcm {
        println!("{:?}", m);
    } else {
        println!("{:?}", ans % MOD);
    }
}