結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1

    m = 100003

    # Initialize XOR128 variables
    global xor128_x, xor128_y, xor128_z, xor128_w
    xor128_x = 123456789
    xor128_y = 362436069
    xor128_z = 521288629
    xor128_w = 88675123

    # Generate A
    A = [0] * N
    for i in range(N):
        t = xor128_x ^ ((xor128_x << 11) & 0xFFFFFFFF)
        t &= 0xFFFFFFFF
        # Update xor128_x, y, z, w
        old_x, old_y, old_z, old_w = xor128_x, xor128_y, xor128_z, xor128_w
        xor128_x = old_y
        xor128_y = old_z
        xor128_z = old_w
        # Compute t ^ (t >> 8)
        t_part = t ^ (t >> 8)
        t_part &= 0xFFFFFFFF
        # Compute new_w
        new_w = old_w ^ ((old_w >> 19) & 0xFFFFFFFF) ^ t_part
        new_w &= 0xFFFFFFFF
        xor128_w = new_w
        # Assign A[i]
        A[i] = xor128_w % m

    # Create presence array
    cnt = [False] * m
    for x in A:
        cnt[x] = True

    # Process queries
    for _ in range(Q):
        q = int(input[ptr])
        ptr += 1
        if q == 0:
            print(0)
            continue
        # Compute inverse of q modulo m
        inv_q = pow(q, m-2, m)
        found = -1
        # Check from m-1 down to 0
        for r in range(m-1, -1, -1):
            a = (r * inv_q) % m
            if cnt[a]:
                found = r
                break
        print(found)

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