結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー Solalyth
提出日時 2026-03-16 15:05:13
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 137 ms / 2,000 ms
コード長 1,300 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,397 ms
コンパイル使用メモリ 201,184 KB
実行使用メモリ 26,112 KB
最終ジャッジ日時 2026-04-17 19:37:34
合計ジャッジ時間 6,327 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_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:46:13
   |
46 |         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: i64 = 998244353;
const INV_2: i64 = 499122177;
const INV_20: i64 = 149736653;

fn f(n: usize) -> i64 {
    let m = n.isqrt() as i64 % M;
    let n = n as i64 % 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 % M * (8*m2 - 5*m - 2) % M * INV_20;
    let t2 = m * (n - m2) % M * (m2 + n - 1) % M * 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 = 1i64;
    
    let mut inv = vec![0, 1];
    for i in 2..=1000000 { inv.push(M - (M/i as i64 * inv[M as usize%i] % M)); }
    for i in 1..=1000000 { assert!(i as i64*inv[i] % 998244353 == 1); }
    
    while L != N {
        while let Some((_, n)) = stk.pop_if(|e| e.0 == L) { cur = cur * inv[n-1] % M * n as i64 % M; }
        let R = stk.last().unwrap().0.min(N);
        ans = (ans + (f(R) - f(L)) * cur) % M;
        L = R;
    }
    
    println!("{}", (ans+M)%M);
}
0