結果

問題 No.3310 mod998
コンテスト
ユーザー 👑 ArcAki
提出日時 2025-10-23 20:43:21
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 3,157 bytes
コンパイル時間 11,488 ms
コンパイル使用メモリ 402,024 KB
実行使用メモリ 8,720 KB
最終ジャッジ日時 2025-10-23 20:43:38
合計ジャッジ時間 15,286 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

// GPT5による生成コード

use std::io::{self, Read};

const MOD: u32 = 998;
const P1: u32 = 2;
const P2: u32 = 499;
const INV2_MOD_499: u32 = 250; // 2 * 250 ≡ 1 (mod 499)

// 十進文字列 s の値を mod で割った余り
fn mod_decimal_str(s: &str, m: u32) -> u32 {
    let mut r: u32 = 0;
    for b in s.bytes() {
        let d = (b - b'0') as u32;
        r = (r * 10 + d) % m;
    }
    r
}

// base^{int(exp_dec)} mod m, exp_dec は十進文字列
fn pow_decimal_exp(mut base: u32, exp_dec: &str, m: u32) -> u32 {
    if m == 1 { return 0; }
    base %= m;
    // precompute base^d (d=0..9)
    let mut small = [1u32; 10];
    for d in 1..10 {
        small[d] = (small[d - 1] * base) % m;
    }
    let mut res: u32 = 1;
    for b in exp_dec.bytes() {
        let d = (b - b'0') as usize;
        // res = res^10 * base^d
        res = mod_pow_u32(res, 10, m);
        res = (res * small[d]) % m;
    }
    res
}

// a^e mod m （e は小さな非負整数、m は 2 or 499）
fn mod_pow_u32(mut a: u32, mut e: u32, m: u32) -> u32 {
    let mut r: u32 = 1;
    a %= m;
    while e > 0 {
        if e & 1 != 0 { r = (r as u64 * a as u64 % m as u64) as u32; }
        a = (a as u64 * a as u64 % m as u64) as u32;
        e >>= 1;
    }
    r
}

// 幾何級数 S = sum_{i=0}^K N^i (mod p)
fn geom_sum_mod_p(n: u32, k_str: &str, p: u32) -> u32 {
    let a = n % p;
    if a == (1 % p) {
        return (mod_decimal_str(k_str, p) + 1) % p;
    }
    // S ≡ (a^{K+1} - 1) * (a-1)^{-1} (mod p)
    // a^{K+1} = a^{K} * a
    let mut t = pow_decimal_exp(a, k_str, p);
    t = (t as u64 * a as u64 % p as u64) as u32; // a^{K+1}
    t = (t + p - 1) % p; // -1
    // p は素数（2, 499）なので (a-1)^{-1} ≡ (a-1)^{p-2}
    let inv = mod_pow_u32((a + p - 1) % p, p - 2, p);
    (t as u64 * inv as u64 % p as u64) as u32
}

// CRT: x ≡ a2 (mod 2), x ≡ a499 (mod 499) を mod 998 で復元
fn crt_2_499(a2: u32, a499: u32) -> u32 {
    // x = a2 + 2 * ((a499 - a2) * inv(2) mod 499)
    let t = (a499 + P2 - (a2 % P2)) % P2;
    let c = (t as u64 * INV2_MOD_499 as u64 % P2 as u64) as u32;
    (a2 + P1 * c) % MOD
}

fn main() {
    // 入力全読み
    let mut s = String::new();
    io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.split_whitespace();

    let t: usize = it.next().unwrap().parse().unwrap();
    let mut out = String::new();

    for _ in 0..t {
        let n: u32 = it.next().unwrap().parse().unwrap();
        let m: usize = it.next().unwrap().parse().unwrap();

        // 早期分岐（n ≡ 0 や n ≡ 1）
        let n_mod = n % MOD;

        for _ in 0..m {
            let k_str = it.next().unwrap(); // 任意長
            let ans = if n_mod == 0 {
                // 0^0=1、以降0 ⇒ 常に 1
                1u32
            } else if n_mod == 1 {
                (mod_decimal_str(k_str, MOD) + 1) % MOD
            } else {
                let a2 = geom_sum_mod_p(n, k_str, P1);
                let a499 = geom_sum_mod_p(n, k_str, P2);
                crt_2_499(a2, a499)
            };
            out.push_str(&format!("{}\n", ans));
        }
    }

    print!("{}", out);
}
0