結果

問題 No.97 最大の値を求めるくえり
コンテスト
ユーザー titia
提出日時 2025-10-22 03:40:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 664 ms / 5,000 ms
コード長 1,019 bytes
コンパイル時間 385 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 86,200 KB
最終ジャッジ日時 2025-10-22 03:40:49
合計ジャッジ時間 6,825 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N,Q=map(int,input().split())

mod=100003

xor128_x = 123456789
xor128_y = 362436069
xor128_z = 521288629
xor128_w = 88675123

def xor128():
    global xor128_x, xor128_y, xor128_z, xor128_w
    t = xor128_x ^ ((xor128_x << 11) & 0xffffffff)
    xor128_x = xor128_y
    xor128_y = xor128_z
    xor128_z = xor128_w
    xor128_w = xor128_w ^ ((xor128_w >> 19) & 0xffffffff) ^ (t ^ ((t >> 8) & 0xffffffff))
    xor128_w &= 0xffffffff  # 32bitに制限
    return xor128_w

def generateA(N):
    A = [0] * N
    for i in range(N):
        A[i] = xor128() % 100003
    return A

A = generateA(N)
SET=set(A)

for tests in range(Q):
    x=int(input())

    if x==0:
        print(0)
    elif N<=500:
        ANS=0
        for a in A:
            ANS=max(ANS,a*x%mod)

        print(ANS)
    else:
        INV=pow(x,mod-2,mod)
        for i in range(mod-1,-1,-1):
            k=i*INV%mod

            if k in SET:
                ANS=i
                break

        print(ANS)
0