[210418][백준/BOJ] 2609번 최대공약수와 최소공배수
문제
입출력
풀이
유클리드 호제법으로 문제를 풀 수 있다.
유클리드 호제법은 두개의 자연수 a, b에서 a를 b로 나눈 나머지 r이라 했을때
GCD(a,b) = GCD(b,r)이고 r이 0이면 그때 b가 최대 공약수라는 원리를 이용한 알고리즘이다.
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
코드
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
while (true)
{
int r = a % b;
if (r == 0)
break;
else
{
a = b;
b = r;
}
}
return b;
}
int lcm(int a, int b)
{
return a * b / gcd(a, b);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
if (m > n)
swap(n, m);
cout << gcd(n, m) << '\n' << lcm(n, m);
}
Author And Source
이 문제에 관하여([210418][백준/BOJ] 2609번 최대공약수와 최소공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kwkim95/210417백준BOJ-2609번-최대공약수와-최소공배수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)