AOJ ALDS1_1_B Greatest Common Divisor

備忘録

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C&lang=ja

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def euclidean_gcd(x, y):
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x = y
        y = r
    return x


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    x, y = il()
    print(euclidean_gcd(x, y))


if __name__ == '__main__':
    main()

考え方

螺旋本より、２つの整数x, yの最大公約数を求める問題。
何も考えずにmath.gcd(x, y)で回答したら通ったが、せっかくなのでユークリッドの互除法を使用した回答を行った。
実装は特に工夫なし。x > yとすることに注意。

---

何も考えずに提出した回答

import math
x,y=map(int,input().split())
print(math.gcd(x, y))