結果

問題 No.1253 雀見椪
ユーザー StrorkisStrorkis
提出日時 2020-10-09 23:30:09
言語 Rust
(1.77.0)
結果
AC  
実行時間 70 ms / 2,000 ms
コード長 1,952 bytes
コンパイル時間 3,879 ms
コンパイル使用メモリ 142,420 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-27 19:52:15
合計ジャッジ時間 5,737 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 5 ms
4,376 KB
testcase_04 AC 64 ms
4,376 KB
testcase_05 AC 64 ms
4,376 KB
testcase_06 AC 68 ms
4,380 KB
testcase_07 AC 64 ms
4,380 KB
testcase_08 AC 67 ms
4,376 KB
testcase_09 AC 65 ms
4,376 KB
testcase_10 AC 70 ms
4,376 KB
testcase_11 AC 68 ms
4,376 KB
testcase_12 AC 66 ms
4,380 KB
testcase_13 AC 67 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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