結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー Solalyth
提出日時 2026-03-16 15:09:11
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 172 ms / 2,000 ms
コード長 1,225 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,259 ms
コンパイル使用メモリ 201,576 KB
実行使用メモリ 34,048 KB
最終ジャッジ日時 2026-04-17 19:37:35
合計ジャッジ時間 3,839 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `N` should have a snake case name
  --> src/main.rs:20:13
   |
20 |         mut N: usize
   |             ^ help: convert the identifier to snake case: `n`
   |
   = note: `#[warn(non_snake_case)]` (part of `#[warn(nonstandard_style)]`) on by default

warning: variable `L` should have a snake case name
  --> src/main.rs:37:13
   |
37 |     let mut L = 1;
   |             ^ help: convert the identifier to snake case: `l`

warning: variable `R` should have a snake case name
  --> src/main.rs:45:13
   |
45 |         let R = stk.last().unwrap().0.min(N);
   |             ^ help: convert the identifier to snake case: `r`

ソースコード

diff #
raw source code 

use proconio::input;

const M: i128 = 998244353;
const INV_2: i128 = 499122177;
const INV_20: i128 = 149736653;

fn f(n: usize) -> i128 {
    let m = n.isqrt() as i128 % M;
    let n = n as i128 % M;
    let m2 = m*m % M;
    
    // (m-1) * m * (m+1) * (m*m*8 - m*5 - 2) / 20 + m * (-m*m + n) * (m*m + n - 1) / 2
    let t = (m2-1) * m * (8*m2 - 5*m - 2) * INV_20;
    let t2 = m * (n - m2) * (m2 + n - 1) * INV_2;
    (t+t2) % M
}

fn main() {
    input! {
        mut N: usize
    }
    
    N += 1;
    
    let mut stk = vec![(N, 0)];
    for k in 3..=60 {
        for n in 2usize.. {
            let x = n.saturating_pow(k);
            if N <= x { break; }
            stk.push((x, n));
        }
    }
    
    stk.sort_unstable(); stk.reverse();
    
    let mut ans = 0;
    let mut L = 1;
    let mut cur = 1;
    
    let mut inv = vec![0, 1];
    for i in 2..=1000000 { inv.push(M - (M/i as i128 * inv[M as usize%i] % M)); }
    
    while L != N {
        while let Some((_, n)) = stk.pop_if(|e| e.0 == L) { cur = cur * inv[n-1] % M * n as i128 % M; }
        let R = stk.last().unwrap().0.min(N);
        ans = (ans + (f(R) - f(L)) * cur) % M;
        L = R;
    }
    
    println!("{}", ans.rem_euclid(M));
}
0