結果

問題 No.3516 Very Large Range Mod
コンテスト
ユーザー yu23578
提出日時 2026-04-16 06:49:57
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 502 ms / 2,000 ms
コード長 1,128 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 352 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 145,212 KB
最終ジャッジ日時 2026-04-24 20:53:34
合計ジャッジ時間 13,245 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# ax + b = 0 (mod M) (0 <= x < c) の解の個数を求める
import math
def kosu(a, b, c, M):
  d = math.gcd(a, M)
  if b % d > 0:
    return 0
  a //= d
  b //= d
  M //= d
  x0 = (-b * pow(a, -1, M)) % M
  if x0 >= c:
    return 0
  return (c - 1 - x0) // M + 1

N, K, M = map(int, input().split())
B = list(map(int, input().split()))
C = list(map(int, input().split()))
def remo(A):
  # AからK個除く
  cnt = K
  S = 0
  while True:
    (x,y) = A.pop()
    S += x * y
    if cnt - x > 0:
      cnt -= x
    elif cnt - x == 0:
      return (S, A)
    else:
      A.append((x - cnt, y))
      S -= (x - cnt) * y
      return (S, A)
X = list(zip(B, C))
(S, P)    = remo(list(reversed(X)))
(dummy, Q)= remo(X)
P.reverse()
# P - Qを計算する
W = []
while len(P) > 0:
  (x0, y0) = P.pop()
  (x1, y1) = Q.pop()
  if x0 < x1:
    W.append((x0, y0 - y1))
    Q.append((x1 - x0, y1))
  elif x0 == x1:
    W.append((x0, y0 - y1))
  else:
    W.append((x1, y0 - y1))
    P.append((x0 - x1, y0))
W.reverse()
# 累積計算
ans = (1 if S % M == 0 else 0)
for (a, b) in W:
  ans += kosu(b % M, S % M, a, M)
  S += a * b
print(ans)
0