https://www.acmicpc.net/problem/2436
2436번: 공약수
첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0
www.acmicpc.net
두 정수 A, B가 주어질 때 A가 최대공약수, B가 최소공배수인 두 수를 찾는 문제입니다.
풀이
조건에 맞는 두 수를 N, M이라고 하면
N,M의 최대공약수는 A, 최소공배수는 B이므로
A×i=N,A×j=M (단, i,j는 서로소)
N×k=B,M×l=B (단, k,l은 서로소)
N,M에 위 식을 대입하면
A×i×k=A×j×l=B
i×k=j×l=B÷A
따라서 B÷A의 약수 중 서로소 조건을 만족하는 i,j,k,l을 찾으면 됩니다.
조건을 만족하는 N,M중 합이 가장 작은 경우를 출력해야 하며,
N+M=A×(i+j)이므로 i,j의 합이 가장 작은 경우를 찾아야 합니다.
i=l,k=j로 두고 B÷A의 약수이면서 서로소인 i,j를 찾으면 답을 구할 수 있습니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(long long a, long long b) {
if (b)
return gcd(b, a % b);
return a;
}
int main() {
long long a, b, d, i = 1;
cin >> a >> b;
d = b / a;
for (long long t = 2; t * t < d; t++) {
if (d % t == 0) {
int n = gcd(t, d / t);
if (n == 1)
i = t;
}
}
cout << a * i << ' ' << a * (d / i);
return 0;
}
|
cs |
사족
혹시 몰라서 다 long long 썼어요
'문제풀이 > 백준' 카테고리의 다른 글
백준 1781번 컵라면 (0) | 2020.10.18 |
---|---|
백준 17298번 오큰수 (0) | 2020.10.18 |
백준 2981번 검문 (0) | 2020.09.08 |
백준 10888번 두 섬간의 이동 (0) | 2020.08.27 |
백준 2660번 회장 뽑기 (0) | 2020.08.17 |