筆者はレート800前後の茶～緑コーダ
ABC297のDを問題を解いていく
実装コード
ユークリッドの互除法を応用してまとめて引き算することができるようだ。
A<Bの場合はスワップして
AとBの商だけA-=Bしたら
AがA%Bだけ残るから
入れ替えてもう一度やる
A=BのときにA%B=0となるからそこで終了
- そのときに+1余分に足されてるから回答は1引く
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
a, b = rLI()
ans = 0
if a < b: a,b=b,a
while b:
ans += a//b
a,b = b, a%b
print(ans-1)
if __name__ == '__main__':
main()
感想
ユークリッドの互除法って典型中の典型アルゴリズムだけど
なかなか覚えられないのは自分だけ？