結果

問題 No.16 累乗の加算
コンテスト
ユーザー srtry
提出日時 2025-05-10 18:39:32
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 1,112 bytes
コンパイル時間 14,485 ms
コンパイル使用メモリ 399,940 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-10 18:39:49
合計ジャッジ時間 15,756 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: constant `big` should have an upper case name
  --> src/main.rs:11:7
   |
11 | const big:usize = 1000003;
   |       ^^^ help: convert the identifier to upper case: `BIG`
   |
   = note: `#[warn(non_upper_case_globals)]` on by default

ソースコード

diff # 

/* 
 *     Author:  srtry
 *     Created: 2025-05-10T06:05:13+09:00
 *     Coding:  utf-8-unix
 */

use proconio::input;
use std::io::{stdout,Write,BufWriter};
use std::collections::HashMap;

const big:usize = 1000003;

fn pow_mod(&x:&usize, &n:&usize, mem:&mut HashMap<usize,usize>) -> usize {
    if mem.contains_key(&n) {
        return mem[&n];
    }

    if n==1 {
        let tmp = x%big;
        mem.insert(1, tmp);
        return x%big;
    } else if n==0 {
        mem.insert(0,1);
        return 1;
    }

    let tmp:usize = pow_mod(&x, &(n/2), mem);
    if n%2 == 0 {
        mem.insert(n, (tmp*tmp)%big);
        return (tmp*tmp)%big;
    } else {
        mem.insert(n, (tmp*tmp*x)%big);
        return (tmp*tmp*x)%big;
    }
}

fn main() {
    input!{
        x:usize, n:usize,
        a:[usize;n]
    }

    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    let mut mem:HashMap<usize,usize> = HashMap::new();

    let mut ans:usize = 0;
    for elem in a.iter() {
        ans += pow_mod(&x, elem, &mut mem);
        ans = ans%big;
    }

    write!(out, "{}", ans).unwrap();
}
0