結果
問題 |
No.141 魔法少女コバ
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:34:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 39 ms / 5,000 ms |
コード長 | 660 bytes |
コンパイル時間 | 224 ms |
コンパイル使用メモリ | 82,272 KB |
実行使用メモリ | 54,432 KB |
最終ジャッジ日時 | 2025-03-31 17:35:20 |
合計ジャッジ時間 | 5,429 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 93 |
ソースコード
import math def solve(M, N): g = math.gcd(M, N) m = M // g n = N // g steps = 0 while True: current_gcd = math.gcd(m, n) m //= current_gcd n //= current_gcd if m == n: return steps if n == 0: return -1 if m > n: q = m // n r = m % n if r == 0: steps += q - 1 m = n else: steps += q m = r else: m, n = n, m steps += 1 return -1 # Read input and output the result M, N = map(int, input().split()) print(solve(M, N))