[백준] 최소공배수

출처:: www.acmicpc.net/problem/1934

분류:: 유클리드 호제법

 

1. 문제 이해 및 해결과정

 - 유클리드 호제법

int gcd(int a, int b)
{
    while (b > 0)
    {
        int tmp = a;
        a = b;
        b = tmp%b;
    }
    return a;
}

 

2. 풀이방법

  1. 유클리드 호제

#최소공배수
#https://www.acmicpc.net/problem/1934
import sys
sys.stdin = open("input.txt","r")
n=int(input())
def LCD(a,b):
    x,y=a,b
    while a>0:#16 (6,10)=6*1+4 ->(4,6)=4*1+2 ->(2,4)=2*2+0 ->(0,2) (나머지,나누는 수)
        # print(a, b)
        tmp=b #tmp=10, 6 , 4
        b=a #b=6, 4, 2
        a=tmp%a #a=4 , 2 , 0

    gcd=b
    return x*y//gcd

for _ in range(n):
    a,b=map(int,input().split())
    print(LCD(a,b))

 

3. 오답원인

 

4. 알게된 점