結果

問題 No.3187 Mingle
ユーザー Mitarushi
提出日時 2025-06-02 22:15:39
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 473 ms / 2,500 ms
コード長 747 bytes
コンパイル時間 12,221 ms
コンパイル使用メモリ 401,784 KB
実行使用メモリ 60,484 KB
最終ジャッジ日時 2025-09-04 02:40:37
合計ジャッジ時間 23,771 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn main() {
    proconio::input! {
        n: usize,
        p: usize,
    }

    let mut divisors = vec![vec![]; n + 1];
    for i in 1..=n {
        for j in (i..=n).step_by(i) {
            divisors[j].push(i);
        }
    }

    let mut invs = vec![0; n + 1];
    invs[1] = 1;
    for i in 2..=n {
        invs[i] = (p - p / i) * invs[p % i] % p;
    }

    let mut dp = vec![0; n + 1];
    let mut total = 0;
    for i in 3..=n {
        let d_sum = divisors[i].iter().map(|&d| dp[d]).sum::<usize>() % p;
        let dp_i = (total + i + p - d_sum) * invs[i - divisors[i].len()] % p;
        for &d in &divisors[i] {
            total = (total + dp_i + p - dp[d]) % p;
            dp[d] = dp_i;
        }
    }

    println!("{}", dp[n]);
}
0