結果

問題 No.3516 Very Large Range Mod
コンテスト
ユーザー detteiuu
提出日時 2026-05-31 17:12:54
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,374 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 231 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 116,280 KB
最終ジャッジ日時 2026-05-31 17:13:13
合計ジャッジ時間 15,473 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import gcd

def inverse(n, d, MOD):
    return n * pow(d, -1, MOD) % MOD

def func(now, diff, cnt):
    if diff == 0:
        if now%M == 0:
            return cnt
        else:
            return 0
    if diff < 0:
        diff = -diff
    else:
        now = (M-now)%M
    GCD = gcd(M, diff)
    if now%GCD != 0:
        return 0
    n = now//GCD
    m = M//GCD
    d = diff//GCD
    c = inverse(n, d, m)
    if cnt <= c:
        return 0
    else:
        return (cnt-c-1)//m+1

N, K, M = map(int, input().split())
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ln, lc = 0, 0
rn, rc = -1, 0
cnt = 0
SUM = 0
for i in range(N):
    if K <= cnt+B[i]:
        diff = K-cnt
        SUM += C[i]*diff
        rn, rc = i, diff-1
        break
    else:
        SUM += C[i]*B[i]
        cnt += B[i]
        rn, rc = i, B[i]-1

ans = 0
while rn < N:
    cnt1, cnt2 = B[ln]-lc, B[rn]-rc
    if cnt1 < cnt2:
        ans += func(SUM, C[rn]-C[ln], cnt1)
        SUM += (C[rn]-C[ln])*cnt1
        ln += 1
        lc = 0
        rc += cnt1
    elif cnt1 > cnt2:
        ans += func(SUM, C[rn]-C[ln], cnt2)
        SUM += (C[rn]-C[ln])*cnt2
        lc += cnt2
        rn += 1
        rc = 0
    else:
        ans += func(SUM, C[rn]-C[ln], cnt1)
        SUM += (C[rn]-C[ln])*cnt1
        ln += 1
        lc = 0
        rn += 1
        rc = 0

print(ans)
0