結果

問題 No.3187 Mingle
ユーザー koba-e964
提出日時 2025-06-29 18:07:03
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 2,283 bytes
コンパイル時間 11,525 ms
コンパイル使用メモリ 402,188 KB
実行使用メモリ 98,304 KB
最終ジャッジ日時 2025-06-29 18:08:15
合計ジャッジ時間 66,183 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

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)
// Tags: sqrt-decomposition, divisors, grouping-by-quotients
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;
        // grouping by quotients
        while sq * sq <= i as u32 {
            sq += 1;
        }
        sq -= 1;
        for b in 1..=sq {
            let to = i as u32 / b * b;
            if to == i as u32 {
                loopback += 1;
            } else {
                me = amod(me, dp[to as usize], p);
            }
        }
        for d in 1..=sq {
            let l = sq.max(i as u32 / (d + 1));
            let mut r = i as u32 / d;
            // (l, r]
            if l >= r {
                continue;
            }
            if r * d == i as u32 {
                loopback += 1;
                r -= 1;
            }
            let dd = d as usize;
            me = amod(me, mul_acc[dd][r as usize + 1], p);
            me = amod(me, p - mul_acc[dd][l as usize+ 1], p);
        }

        // (me + i) / non_loopback
        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