結果
| 問題 | No.3179 3 time mod |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-17 21:40:21 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 33 ms / 2,000 ms |
| + 880µs | |
| コード長 | 2,043 bytes |
| 記録 | |
| コンパイル時間 | 81 ms |
| コンパイル使用メモリ | 64,108 KB |
| 実行使用メモリ | 53,804 KB |
| 最終ジャッジ日時 | 2026-11-17 21:40:27 |
| 合計ジャッジ時間 | 3,675 ms |
|
ジャッジサーバーID (参考情報) |
judge5_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 42 |
ソースコード
import math
def extended_euclid(a, b):
# ax + by = 1 (aとbが互いに素の場合) または gcd(a,b) の解を求める
c, d, e, f = 1, 0, 0, 1
while b:
q = a // b
c, d = d, c - q * d
e, f = f, e - q * f
a, b = b, a % b
return (c, e)
def ax_by_c(a, b, c):
# ax + by = c を満たす (x, y) を求める
sign_a = a < 0
sign_b = b < 0
a = abs(a)
b = abs(b)
g2 = math.gcd(a, b)
if c % g2 != 0:
return None, None # 解なし
x, y = extended_euclid(a // g2, b // g2)
x *= (c // g2)
y *= (c // g2)
if sign_a:
x = -x
if sign_b:
y = -y
return x, y
def crt_2(r1, m1, r2, m2):
"""
2つの合同式 x ≡ r1 (mod m1) と x ≡ r2 (mod m2) を1つにまとめる。
戻り値: (r3, m3) 新しい合同式 x ≡ r3 (mod m3)。解がない場合は (0, -1)
"""
# 求めたいのは m1 * k1 + r1 = m2 * (-k2) + r2
# つまり、m1 * k1 + m2 * k2 = r2 - r1 となる k1 (と k2)
k1, k2 = ax_by_c(m1, m2, r2 - r1)
if k1 is None:
return 0, -1 # 矛盾している場合
# x = m1 * k1 + r1
m3 = (m1 * m2) // math.gcd(m1, m2)
r3 = (m1 * k1 + r1) % m3
return r3, m3
def solve(N, A, B, C, P, Q, R):
# 1. まず A (mod P) と B (mod Q) をまとめる
r12, m12 = crt_2(A, P, B, Q)
if m12 == -1:
return 0 # 良い数が存在しない
# 2. 次に、まとめた結果と C (mod R) をまとめる
r_all, m_all = crt_2(r12, m12, C, R)
if m_all == -1:
return 0 # 良い数が存在しない
# 3. 0以上 PQR 未満での唯一の良い数は r_all になる。
# 周期は m_all (P, Q, R の最小公倍数)
# N 以下の範囲にある「良い数」の個数を数える
if N < r_all:
return 0
return (N - r_all) // m_all + 1
if __name__ == "__main__":
N = int(input())
P, Q, R = map(int, input().split())
A, B, C = map(int, input().split())
ans = solve(N, A, B, C, P, Q, R)
print(ans)