[BOJ]2609|最大公約数と最小公倍数


2609|最大公倍数および最小公倍数
https://www.acmicpc.net/problem/2609


マイコード

a, b = map(int, input().split())

# 최대 공약수
for i in range(min(a,b), 0, -1):
    if a%i == 0 and b%i == 0:
        print(i)
        break

# 최소 공배수
for i in range(max(a,b), a*b+1, max(a,b)):
    if i%a == 0 and i%b == 0:
        print(i)
        break

理想的なコード

def get_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def get_lcm(a, b):
    return a * b // get_gcd(a, b)


a, b = map(int, input().split())
print(get_gcd(a, b))
print(get_lcm(a, b))
  • ユークリディアン湖製法
  • 勉強する


  • aをbで割った残りの(mod)およびbの最大公約数(gcd)は、aおよびbの最大公約数(gcd)に等しい

  • 最小公倍数(lcm)は、2つの数の積を最大公倍数で割ったものである.