結果

問題 No.3179 3 time mod
ユーザー LyricalMaestro
提出日時 2025-06-17 00:03:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 44 ms / 2,000 ms
コード長 819 bytes
コンパイル時間 427 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 53,828 KB
最終ジャッジ日時 2025-06-17 00:03:29
合計ジャッジ時間 4,479 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/3179

def ext_euclide(X, Y):
    """
    拡張ユークリッド互除法を実行する。
    a * X + b * Y = 1 を満たすa, bを取得する
    X, Yの満たすべき前提として
    ・gcd(X, Y) = 1
    ・X > Y
    ・X > 0, Y > 0
    """
    if Y == 1:
        return 0, 1

    a, b = ext_euclide(Y, X % Y)
    return b, a - b * (X // Y)

def main():
    N = int(input())
    P, Q, R = map(int, input().split())
    A, B, C = map(int, input().split())

    a, b =  ext_euclide(P, Q)
    x = a * P * B + A * b * Q
    x %= P * Q

    c, d = ext_euclide(P *Q, R)

    y = c * P * Q * C + x * R * d
    y %= (P * Q * R)

    if y > N:
        print(0)
    else:
        z = N - y
        z_ = z // (P * Q * R) + 1
        print(z_)




if __name__ == "__main__":
    main()
0