結果

問題 No.3179 3 time mod
コンテスト
ユーザー Prala
提出日時 2025-06-13 22:36:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 904 bytes
コンパイル時間 463 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 60,548 KB
最終ジャッジ日時 2025-06-13 22:36:46
合計ジャッジ時間 3,657 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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(2*10**6):
    if (pq + i * G) % R ==C:
        min_pqr = pq + i * G
        break

if min_pqr == 10**18+2:
    print(0)
    exit()
if min_pqr+math.lcm(P, Q, R) > N:
	print(1)
	exit()

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

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