結果
問題 |
No.3179 3 time mod
|
ユーザー |
![]() |
提出日時 | 2025-06-24 05:29:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 1,797 bytes |
コンパイル時間 | 485 ms |
コンパイル使用メモリ | 82,168 KB |
実行使用メモリ | 54,476 KB |
最終ジャッジ日時 | 2025-06-24 05:29:07 |
合計ジャッジ時間 | 4,432 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 42 |
ソースコード
from math import lcm import math def CRT(rem_pair, mod_pair): """ rem_pair = (r1,r2) mod_pair = (m1,m2) とします。この時m1,m2がどちらも0ではないとします。 この時 x = m1 (mod r1) x = m2 (mod r2) となる整数xが存在する場合、0以上の最小の自然数を返します。 存在しない場合は-1を返します。 """ r1, r2 = rem_pair m1, m2 = mod_pair assert (m1 != 0 and m2 != 0) assert len(rem_pair) == len(mod_pair) == 2 g = math.gcd(m1, m2) if (r2 - r1) % g != 0: return -1 M1, M2, R = m1//g, (-m2)//g, (r2 - r1)//g inv = pow(M1, -1, M2) * R % M2 return (m1*inv + r1) % abs(m1*m2//g) def many_CRT(rem_pair, mod_pair): """ rem_pair = (r1,r2...r_t) mod_pair = (m1,m2...r_t) とします。この時m1,m2......m_tはいずれも0ではないとします。 この時 x = m1 (mod r1) x = m2 (mod r2) . . . x = m_t (mod r_t) となる整数xが存在する場合、0以上の最小の自然数を返します。 存在しない場合は-1を返します。 """ assert len(rem_pair) == len(mod_pair) assert all(elem != 0 for elem in mod_pair) M, LCM = CRT(rem_pair[:2], mod_pair[:2]), mod_pair[0] * \ mod_pair[1]//math.gcd(mod_pair[0], mod_pair[1]) for (r, m) in zip(rem_pair[2:], mod_pair[2:]): if M == -1: return -1 M = CRT((r, M), (m, LCM)) LCM = LCM * m // math.gcd(LCM, m) return M N = int(input()) P,Q,R = list(map(int,input().split())) A,B,C = list(map(int,input().split())) min_good = many_CRT([A,B,C],[P,Q,R]) LCM = lcm(P,Q,R) x = (N - min_good)//LCM print(x+1)