結果

問題 No.1164 GCD Products hard
ユーザー titia
提出日時 2025-08-20 01:51:38
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 1,950 bytes
コンパイル時間 10,500 ms
コンパイル使用メモリ 403,204 KB
実行使用メモリ 158,276 KB
最終ジャッジ日時 2025-08-20 01:52:32
合計ジャッジ時間 49,812 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26 TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `std::cmp`
 --> src/main.rs:2:5
  |
2 | use std::cmp;
  |     ^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

ソースコード

diff # 

use std::io;
use std::cmp;

fn modpow(mut base: i64, mut exp: i64, modu: i64) -> i64 {
    let mut result = 1i64;
    base %= modu;
    while exp > 0 {
        if exp & 1 == 1 {
            result = (result * base) % modu;
        }
        base = (base * base) % modu;
        exp >>= 1;
    }
    result
}

fn main() {
    // 入力
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let nums: Vec<i64> = input.split_whitespace().map(|x| x.parse::<i64>().unwrap()).collect();
    let a = nums[0];
    let b = nums[1];
    let n = nums[2];

    let modu: i64 = 1_000_000_007;
    let modu2: i64 = modu - 1;

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

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

    // 素数列挙
    let limit: usize = 10_000_001; // 10^7 + 1
    let mut primelist: Vec<i64> = (0..=limit as i64).collect();
    primelist[1] = 0;
    let l = (limit as f64).sqrt().floor() as i64;

    for i in 2..=limit as i64 {
        if i > l {
            break;
        }
        if primelist[i as usize] == 0 {
            continue;
        }
        let mut j = 2 * i;
        while j <= limit as i64 {
            primelist[j as usize] = 0;
            j += i;
        }
    }

    let primes: Vec<i64> = primelist.into_iter().filter(|&v| v != 0).collect();

    for &p in primes.iter() {
        let mut i = 1;
        loop {
            let idx = i * p;
            if idx > b {
                break;
            }
            let idx_usize = idx as usize;
            let i_usize = i as usize;
            x[i_usize] -= x[idx_usize];
            i += 1;
        }
    }

    let mut ans: i64 = 1;
    for i in 2..=b {
        let xi = ((x[i as usize] % modu2) + modu2) % modu2; // 念のため非負に
        ans = (ans * modpow(i, xi, modu)) % modu;
    }

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