結果

問題 No.97 最大の値を求めるくえり
ユーザー gew1fw
提出日時 2025-06-12 16:31:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,794 bytes
コンパイル時間 481 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 95,616 KB
最終ジャッジ日時 2025-06-12 16:32:23
合計ジャッジ時間 16,332 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 100003

def modinv(a, mod):
    g, x, y = extended_gcd(a, mod)
    if g != 1:
        return None  # Inverse doesn't exist if a and mod are not coprime
    else:
        return x % mod

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def generateA(N):
    xor128_x = 123456789
    xor128_y = 362436069
    xor128_z = 521288629
    xor128_w = 88675123
    A = []
    for _ in range(N):
        t = xor128_x ^ (xor128_x << 11)
        t = t & 0xFFFFFFFF  # Ensure it's 32-bit
        xor128_x = xor128_y
        xor128_y = xor128_z
        xor128_z = xor128_w
        xor128_w = (xor128_w ^ (xor128_w >> 19)) ^ (t ^ (t >> 8))
        a = xor128_w % MOD
        A.append(a)
    return A

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    Q = int(input[ptr])
    ptr +=1
    queries = []
    for _ in range(Q):
        q = int(input[ptr])
        queries.append(q)
        ptr +=1

    A = generateA(N)
    present = [False] * MOD
    for a in A:
        present[a] = True

    # Precompute modular inverses for all q in 1..MOD-1
    inv = [0] * MOD
    for q in range(1, MOD):
        inv[q] = modinv(q, MOD)

    # Precompute maximum a in A
    max_a = max(A) if A else 0

    for q in queries:
        if q == 0:
            print(0)
            continue
        q_inv = inv[q]
        a_max = ((MOD -1) * q_inv) % MOD
        if present[a_max]:
            print(MOD -1)
        else:
            current_max = 0
            for a in A:
                val = (q * a) % MOD
                if val > current_max:
                    current_max = val
            print(current_max)

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