結果

問題 No.97 最大の値を求めるくえり
ユーザー lam6er
提出日時 2025-03-20 20:34:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,320 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 89,664 KB
最終ジャッジ日時 2025-03-20 20:35:22
合計ジャッジ時間 9,245 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 100003

def xor128():
    global xor128_x, xor128_y, xor128_z, xor128_w
    t = xor128_x ^ ((xor128_x << 11) & 0xFFFFFFFF)
    t ^= (t >> 8)
    xor128_x, xor128_y, xor128_z = xor128_y, xor128_z, xor128_w
    new_w = (xor128_w ^ ((xor128_w >> 19) & 0xFFFFFFFF)) ^ t
    new_w &= 0xFFFFFFFF
    xor128_w = new_w
    return xor128_w

def generateA(N):
    A = []
    for _ in range(N):
        val = xor128() % MOD
        A.append(val)
    return A

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, Q = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    queries = [int(input[ptr+i]) for i in range(Q)]
    # Initialize xor128 state
    global xor128_x, xor128_y, xor128_z, xor128_w
    xor128_x, xor128_y, xor128_z, xor128_w = 123456789, 362436069, 521288629, 88675123
    # Generate array A
    A = generateA(N)
    # Preprocess exist array
    exist = [False] * MOD
    for a in A:
        exist[a] = True
    # Process queries
    for q in queries:
        if q ==0:
            print(0)
            continue
        inv_q = pow(q, MOD-2, MOD)
        found = -1
        for k in range(MOD-1, -1, -1):
            target_a = (k * inv_q) % MOD
            if exist[target_a]:
                found = k
                break
        print(found)

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