結果

問題 No.3187 Mingle
コンテスト
ユーザー koba-e964
提出日時 2025-06-29 17:53:42
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 2,502 bytes
コンパイル時間 13,876 ms
コンパイル使用メモリ 398,084 KB
実行使用メモリ 98,384 KB
最終ジャッジ日時 2025-06-29 17:55:04
合計ジャッジ時間 70,416 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok().unwrap();
    ret
}

fn amod(a: i64, b: i64, p: i64) -> i64 {
    let mut r = a + b;
    if r >= p {
        r -= p;
    }
    r
}

fn powmod(x: i64, mut e: i64, m: i64) -> i64 {
    let mut sum = 1;
    let mut cur = x % m;
    while e > 0 {
        if e % 2 != 0 {
            sum = sum * cur % m;
        }
        cur = cur * cur % m;
        e /= 2;
    }
    sum
}

// https://yukicoder.me/problems/no/3187 (3)
fn main() {
    let ints = getline()
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<i64>().unwrap())
        .collect::<Vec<_>>();
    let n = ints[0] as usize;
    let p = ints[1];
    let mut dp = vec![0; n + 1];
    let mut divs = vec![vec![]; n + 1];
    for i in 1..=n {
        for j in (i..=n).step_by(i) {
            divs[j].push(i);
        }
    }
    let mut mul_acc = vec![vec![]; n + 1];
    for i in 1..=n {
        mul_acc[i] = vec![0; n / i + 2];
    }
    for i in 3..=n {
        let mut loopback = 0;

        let mut sq = 0;
        let mut me = 0;
        while sq * sq <= i {
            sq += 1;
        }
        sq -= 1;
        for b in 1..=sq {
            let to = i / b * b;
            if to == i {
                loopback += 1;
            } else {
                me = amod(me, dp[to], p);
            }
        }
        for d in 1..=sq + 1 {
            let l = sq.max(i / (d + 1));
            let mut r = i / d;
            // (l, r]
            if l >= r {
                continue;
            }
            if r * d == i {
                loopback += 1;
                r -= 1;
            }
            me = amod(me, mul_acc[d][r + 1], p);
            me = amod(me, p - mul_acc[d][l + 1], p);
        }

        // (me + i) / non_loopback
        // naive
        if false {
            let mut non_loopback = i;
            let mut naive_me = 0;
            for j in 1..= i {
                if i / j * j == i {
                    non_loopback -= 1;
                } else {
                    naive_me = amod(naive_me, dp[i / j * j], p);
                }
            }
            eprintln!("naive: {} {}", i - non_loopback, naive_me);
        }
        me = amod(me, i as i64, p);
        dp[i] = me * powmod(i as i64 - loopback, p - 2, p) % p;
        for &d in &divs[i] {
            let j = i / d;
            mul_acc[d][j + 1] = amod(mul_acc[d][j], dp[i], p);
        }
    }
    println!("{}", dp[n]);
}
0