문제

정수 B를 0보다 큰 정수인 N으로 곱해 정수 A를 구할 수 있다면 A는 B의 배수이다.

예:

• 10은 5의 배수이다 (5 * 2 = 10)
• 10은 10의 배수이다(10 * 1 = 10)
• 6은 1의 배수이다(1 * 6 = 6)
• 20은 1, 2, 4, 5, 10, 20의 배수이다.

다른 예:

• 2와 5의 최소공배수는 10이고, 그 이유는 10은 2와 5 둘 다의 배수이고, 10보다 작은 공배수가 없기 때문이다.
• 10과 20의 최소공배수는 20이다.
• 5와 3의 최소공배수는 15이다.
• 당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.

---

입력

한 줄에 두 자연수 A와 B가 공백으로 분리되어 주어진다.

A와 B는 100,000,000(10^8)보다 작다.

참고: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int(%lld)를 사용하고, Java에서는 long을 사용하시오.

---

출력

A와 B의 최소공배수를 한 줄에 출력한다.

---

예제 입력

121 199

---

예제 출력

24079

---

아이디어

최소공배수를 구하려면 최대 공약수가 필요하다. 최대공약수를 구할 때 유클리드 호제법을 사용했다. 유클리드 호제법을 간단하게 설명하면 gcd(x,y)라는 함수가 x, y의 최대공약수를 구하는 함수라고 가정하면 gcd(x,y) = gcd(y,x%y)가 성립하게 된다는 알고리즘이다. 예를들어 3과 15의 최소공배수를 구하려고 하면 일단 유클리드 호제법을 이용하여 최대공약수를 구한다. 3과 15의 최대공약수는 3이다. 최대공약수를 구했으면 3과 15를 곱한값 즉 45에 최대공약수를 나누면 최소공배수가 나온다. 즉 45 / 3 = 15 따라서 최소공배수는 15이다. 이 개념을 바탕으로 코드를 작성했다.

---

코드

풀이보기(클릭)

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

while bb!=0:
    aa=aa%bb
    aa,bb=bb,aa

print(a*b//aa)

---

문제 출처

2016 AIPO National Finals 2번