結果

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

ソースコード

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

    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 z array
    z = [0] * MOD

    # Process eels for i=1 to M
    for i in range(M):
        x_i = X[i]
        y_i = Y[i]
        z[x_i] += y_i

    # Generate eels for i=M+1 to N
    if M < N:
        x_prev = X[-1]
        y_prev = Y[-1]
        for i in range(M, N):
            x_i = (x_prev * mulX + addX) % MOD
            y_i = (y_prev * mulY + addY) % MOD
            z[x_i] += y_i
            x_prev, y_prev = x_i, y_i

    # Precompute sum_d
    sum_d = [0] * MOD
    for d in range(1, MOD):
        sum_d[d] = sum(z[k] for k in range(0, MOD, d))

    # Process rabbits
    xor_all = 0
    output_M = []

    # Process first M rabbits
    for j in range(M):
        a_j = A[j]
        b_j = B[j]
        m_j = a_j * b_j
        if m_j >= MOD:
            ans_j = sum_d[a_j]
        else:
            if m_j < MOD:
                ans_j = sum_d[a_j] - sum_d[m_j]
            else:
                ans_j = sum_d[a_j]
        output_M.append(ans_j)
        xor_all ^= ans_j

    # Generate rabbits for j=M+1 to N
    if M < N:
        a_prev = A[-1]
        b_prev = B[-1]
        for j in range(M, N):
            a_j = (a_prev * mulX + addX + MOD - 1) % MOD + 1
            b_j = (b_prev * mulY + addY + MOD - 1) % MOD + 1
            m_j = a_j * b_j
            if m_j >= MOD:
                ans_j = sum_d[a_j]
            else:
                if m_j < MOD:
                    ans_j = sum_d[a_j] - sum_d[m_j]
                else:
                    ans_j = sum_d[a_j]
            xor_all ^= ans_j
            a_prev, b_prev = a_j, b_j

    # Output
    for ans in output_M:
        print(ans)
    print(xor_all)

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