結果

問題 No.1164 GCD Products hard
ユーザー titia
提出日時 2025-08-19 20:10:41
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,321 bytes
コンパイル時間 11,918 ms
コンパイル使用メモリ 399,548 KB
実行使用メモリ 87,868 KB
最終ジャッジ日時 2025-08-19 20:11:44
合計ジャッジ時間 59,329 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 18 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::{self, Read};

const MOD: i64 = 1_000_000_007;

// a^b mod m を計算する関数
fn mod_pow(mut a: i64, mut b: i64, m: i64) -> i64 {
    let mut res = 1i64;
    a %= m;
    while b > 0 {
        if b & 1 == 1 {
            res = res * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    res
}

fn main() {
    // 入力を読み込み
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();
    let a: i64 = it.next().unwrap().parse().unwrap();
    let b: i64 = it.next().unwrap().parse().unwrap();
    let n: i64 = it.next().unwrap().parse().unwrap();

    // X 配列
    let mut x = vec![0i64; (b + 1) as usize];

    for i in 2..=b {
        let ko = b / i - (a - 1) / i;
        x[i as usize] = mod_pow(ko, n, MOD);
    }

    for i in (1..=b).rev() {
        let mut score = 0i64;
        let mut j = i + i;
        while j <= b {
            score += x[j as usize];
            j += i;
        }
        x[i as usize] -= score;
        x[i as usize] = (x[i as usize] % MOD + MOD) % MOD; // 念のため正規化
    }

    let mut ans = 1i64;
    for i in 1..=b {
        if x[i as usize] != 0 {
            ans = ans * mod_pow(i as i64, x[i as usize], MOD) % MOD;
        }
    }

    println!("{}", ans);
}
0