分類:数学、整数論、ユークリッドアーク法

1.質問

プログラムを作成し、2つの自然数を入力し、最大公約数と最小公約数を出力してください.
ソース:https://www.acmicpc.net/problem/2609

2.アイデア

ユークリッド湖製法
mine

最大公約数(gcdを使用)

を求める

の最小の公倍数を求めます(2つの数の積はgcdで割ります)
ソース:https://velog.io/@onejh96__/CodeUp1092
someone

最大公約数(gcdを使用)

を求める

最小公倍数を求める(lcmを使用)
出典:https://www.acmicpc.net/source/25380750

3.コード

mine

from math import gcd

a, b = map(int, input().split())
gcdNum = gcd(a,b)
lcmNum = a*b//(gcdNum)
print(gcdNum)
print(lcmNum)

ソース:https://github.com/Gitgorithm/wogus0333_Github/blob/main/BOJ/BOJ_2609.py
someone

import math

a, b = map(int, input().split())
print(math.gcd(a, b))
print(math.lcm(a, b))

4.改善

コードが簡潔になり、68 ms->60 msで8 msの時間短縮効果があります.gcdを知ってlcmを知らない私は...男子