結果

問題 No.1253 雀見椪
コンテスト
ユーザー Strorkis
提出日時 2020-10-09 23:30:09
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 68 ms / 2,000 ms
コード長 1,952 bytes
コンパイル時間 12,363 ms
コンパイル使用メモリ 376,716 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-20 14:22:27
合計ジャッジ時間 14,064 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

macro_rules! read_to_tuple {
    ( $( $t:ty ),* ) => {{
        let mut input = String::new();
        std::io::stdin().read_line(&mut input).unwrap();
        let mut iter = input.split_whitespace();
        ( $( iter.next().unwrap().parse::<$t>().unwrap() ),* )
    }}
}

const MOD: i64 = 1_000_000_007;

fn gcd(a: i64, b: i64) -> i64 {
    let r = a % b;
    if r != 0 { gcd(b, r) } else { b }
}

fn lcm(a: i64, b: i64) -> i64 {
    a / gcd(a, b) * b
}

fn pow(mut a: i64, mut n: i64) -> i64 {
    let mut res = 1;
    while n > 0 {
        if n & 1 > 0 {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        n >>= 1;
    }
    res
}

fn solve() -> String {
    let (n, mut ag, mut bg, mut ac, mut bc, mut ap, mut bp) = {
        read_to_tuple!(i64, i64, i64, i64, i64, i64, i64)
    };
    
    let f = |a: &mut i64, b: &mut i64| {
        let x = gcd(*a, *b);
        *a /= x;
        *b /= x;
    };
    
    f(&mut ag, &mut bg);
    f(&mut ac, &mut bc);
    f(&mut ap, &mut bp);

    let g = |al: i64, bl: i64, ar: i64, br: i64| -> i64 {
        let mut res = 1;
        let x = lcm(bl, br);
        res = res * pow((al * (x / bl) + ar * (x / br)) % MOD, n) % MOD;
        res = res * pow(pow(x % MOD, n), MOD - 2) % MOD;
        res
    };

    let h = |a: i64, b: i64| -> i64 {
        let mut res = 1;
        res = res * pow(a, n) % MOD;
        res = res * pow(pow(b, n), MOD - 2);
        res
    };

    let mut ans = 0;
    ans = (ans + g(ag, bg, ac, bc)) % MOD;
    ans = (ans + g(ac, bc, ap, bp)) % MOD;
    ans = (ans + g(ap, bp, ag, bg)) % MOD;
    ans = (ans + MOD - h(ag, bg) * 2 % MOD) % MOD;
    ans = (ans + MOD - h(ac, bc) * 2 % MOD) % MOD;
    ans = (ans + MOD - h(ap, bp) * 2 % MOD) % MOD;    
    ans = (1 + MOD - ans) % MOD;
    ans.to_string()
}

fn main() {
    let t = read_to_tuple!(usize);
    let answers = (0..t).map(|_| solve()).collect::<Vec<_>>();
    println!("{}", answers.join("\n"));
}
0