(1934) 최소공배수

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

단계별로 풀어보기

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

 

 

 

a*b=gcd(a,b)*LCM(a,b)라는 정수론의 간단한 배경지식을 알면 쉽게 풀리는 문제

브루트 포스로 풀어도 T가 1000이고 max(A,B)가 45000이므로 1000*45000=4500만은 시간 내에 충분히 돌아간다.

물론 유클리드 호제법을 쓰면 더 간단하지만 호제법은 다음 문제의 정해라서 일부러 안 썼다.

 

 

 

#include <iostream>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    int a, b;
    
    cin >> a >> b;
    
    for(int x=min(a,b);;x--){
      if(a%x==0 && b%x==0){
        cout << a*b/x << "\n";
        
        break;
      }
    }
  }
  
  return 0;
}