結果

問題 No.3179 3 time mod
ユーザー Prala
提出日時 2025-06-13 22:11:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 850 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 60,472 KB
最終ジャッジ日時 2025-06-13 22:11:18
合計ジャッジ時間 3,429 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def IM(): return map(int, input().split())
def IL()->list[int]: return [int(i) for i in input().split()]

def extended_euclid(a, b):
    if b == 0:
        return a, 1, 0
    d, x1, y1 = extended_euclid(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return d, x, y

def crt(a, A, b, B):
    d, x, y = extended_euclid(A, B)
    if (b - a) % d != 0:
        return -1
    k = (b - a) // d
    mod = A * B // d
    x = (a + A * ((k * x) % (B // d))) % mod
    return x

N = int(input())
P, Q, R = IM()
A, B, C = IM()

pq = crt(A, P, B, Q)
if pq == -1:
    print(0)
    exit()

G = math.gcd(P, Q, R)
min_pqr = 10**18+2

for i in range(10**6):
    if (pq + i * G) % R ==C:
        min_pqr = pq + i * G
        break

if min_pqr == 10**18+2:
    print(0)
    exit()

d, m = divmod(N, math.lcm(P, Q, R))

print(d +1 if m <= min_pqr else d)
0