結果

問題 No.3310 mod998
コンテスト
ユーザー chiaoi
提出日時 2025-10-23 23:46:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 603 ms / 2,000 ms
コード長 1,719 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 83,296 KB
最終ジャッジ日時 2025-10-23 23:47:08
合計ジャッジ時間 16,238 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import set_int_max_str_digits
set_int_max_str_digits(0)

def pow_mod(a, x, mod):
    res = 1
    a %= mod
    while x > 0:
        if x & 1 == 1:
            res = (res * a) % mod
        a = (a * a) % mod
        x >>= 1
    return res

def mod_inv(a, mod):
    def extended_gcd(a, b):
        if b == 0:
            return a, 1, 0
        gcd, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return gcd, x, y
    
    gcd, x, _ = extended_gcd(a % mod, mod)
    if gcd != 1:
        return None
    return (x % mod + mod) % mod

def geometric_sum(n, k, mod):
    n %= mod
    if n == 0:
        return 1 % mod
    if n == 1:
        return (k + 1) % mod
    
    inv = mod_inv((n - 1) % mod, mod)
    if inv is None:
        result = 0
        power = 1
        for _ in range(min(k + 1, mod)):
            result = (result + power) % mod
            power = (power * n) % mod
        return result
        
    k_plus_1_reduced = (k % (mod - 1)) + 1
    if k_plus_1_reduced == mod:
        k_plus_1_reduced = 1
    
    numerator = (pow_mod(n, k_plus_1_reduced, mod) - 1 + mod) % mod
    return (numerator * inv) % mod

def chinese_remainder_theorem(a1, a2):
    inv2 = mod_inv(2, 499)
    t = ((a2 - a1) * inv2) % 499
    return (a1 + 2 * t) % 998

def main():
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        for _ in range(m):
            k = int(input())
            
            result_mod2 = geometric_sum(n, k, 2)
            result_mod499 = geometric_sum(n, k, 499)
            
            result = chinese_remainder_theorem(result_mod2, result_mod499)
            print(result)

if __name__ == "__main__":
    main()
0