(13241) 최소공배수

https://www.acmicpc.net/problem/13241

단계별로 풀어보기

15단계(약수, 배수와 소수 2) 2번째

 

 

 

유클리드 호제법을 구현하는 코드는 재귀도 있고 여러가지가 있지만 반복문, 그 중에서도 pair를 이용하는 코드를 제일 선호한다.

임시 변수를 만들 필요 없이 한 줄로 깔끔하게 쓸 수 있기 때문이다. (특히 확장 유클리드 알고리즘에서 pair를 이용하면 정말 깔끔해진다.)

 

 

 

#include <iostream>
using namespace std;

long gcd(int a, int b){
  pair<long,long> p= {a,b};
  
  while(p.second)  p= {p.second, p.first%p.second};
  
  return p.first;
}

int main() 
{
  long a, b;
  
  cin >> a >> b;
  
  cout << a*b/gcd(a,b);
  
  return 0;
}