結果

問題 No.896 友達以上恋人未満
ユーザー gew1fw
提出日時 2025-06-12 18:27:54
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,134 bytes
コンパイル時間 135 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 650,864 KB
最終ジャッジ日時 2025-06-12 18:28:10
合計ジャッジ時間 13,393 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0

    M = int(input[ptr])
    ptr +=1
    N = int(input[ptr])
    ptr +=1
    mulX = int(input[ptr])
    ptr +=1
    addX = int(input[ptr])
    ptr +=1
    mulY = int(input[ptr])
    ptr +=1
    addY = int(input[ptr])
    ptr +=1
    MOD = int(input[ptr])
    ptr +=1

    # Read X, Y, A, B for the first M elements
    X = list(map(int, input[ptr:ptr+M]))
    ptr += M
    Y = list(map(int, input[ptr:ptr+M]))
    ptr += M
    A = list(map(int, input[ptr:ptr+M]))
    ptr += M
    B = list(map(int, input[ptr:ptr+M]))
    ptr += M

    # Initialize x, y, a, b arrays (1-based)
    x = [0] * (N + 1)
    y = [0] * (N + 1)
    a = [0] * (N + 1)
    b = [0] * (N + 1)

    x[1:M+1] = X[:]
    y[1:M+1] = Y[:]
    a[1:M+1] = A[:]
    b[1:M+1] = B[:]

    for i in range(M+1, N+1):
        x_prev = x[i-1]
        x_i = (x_prev * mulX + addX) % MOD
        x[i] = x_i

        y_prev = y[i-1]
        y_i = (y_prev * mulY + addY) % MOD
        y[i] = y_i

        a_prev = a[i-1]
        a_i = (a_prev * mulX + addX + MOD - 1) % MOD + 1
        a[i] = a_i

        b_prev = b[i-1]
        b_i = (b_prev * mulY + addY + MOD - 1) % MOD + 1
        b[i] = b_i

    # Build z array
    z = [0] * MOD
    for i in range(1, N+1):
        xi = x[i]
        yi = y[i]
        z[xi] += yi

    # Precompute S[d] for all d from 1 to MOD
    S = [0] * (MOD + 1)
    for d in range(1, MOD + 1):
        total = 0
        k = 0
        while k < MOD:
            total += z[k]
            k += d
        S[d] = total

    # Process each rabbit and compute the answer
    xor_sum = 0
    output = []
    for j in range(1, N+1):
        aj = a[j]
        bj = b[j]
        d1 = aj
        d2 = aj * bj
        if d2 > MOD:
            current = S[d1]
        else:
            if d2 > MOD:
                current = S[d1]
            else:
                current = S[d1] - S[d2]
        if j <= M:
            output.append(str(current))
        xor_sum ^= current

    # Output the results
    print('\n'.join(output))
    print(xor_sum)

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