알고리즘 문제풀이/백준
[C++] 백준 2436 - 공약수
알고수가될남자
2020. 4. 27. 20:37
https://www.acmicpc.net/problem/2436
2436번: 공약수
첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.
www.acmicpc.net
<풀이>
1. 최대공약수 최소공배수를 입력받고, 최소공배수를 최대공약수로 나눈 숫자를 구한다.
2. 그 숫자들의 약수 짝(두 약수를 곱해서 다시 그 숫자가 되는 두 수)을 구한다.
3. 약수 짝이 서로소인 것을 구한다.
4. 약수 짝(두 수)에 각각 최대공약수를 곱하면, 정답이 가능한 두 수가 된다.
5. 가능한 두 수 중 합이 가장 작은 것을 출력한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <iostream>
#include <cmath>
using namespace std;
long long int gcd, lcm, tmp;
long long int resA = 0, resB = 0;
int main() {
//입력
cin >> gcd >> lcm;
//tmp = 최소공배수 / 최대공약수
tmp = lcm / gcd;
//tmp의 약수 두 수 구하고, 서로소인지 판별
for (long long int i = 1; i * i <= tmp; i++) {
if (tmp % i == 0) {
//약수 두 수
long long int tmpA = i;
long long int tmpB = tmp / i;
//약수 두 수가 서로소인지 판별
bool isAble = true;
long long int cnt = 0;
for (long long int j = 1; j <= tmpA; j++) {
if (tmpA % j == 0 && tmpB % j == 0) {
cnt++;
}
//약수의 개수가 1개보다 많은 경우 불가능
if (cnt > 1) {
isAble = false;
break;
}
}
//가능한 경우 중 가장 마지막에 저장되는 값이 합이 가장 작게된다
if (isAble) {
resA = tmpA * gcd;
resB = tmpB * gcd;
}
}
}
//출력
cout << resA << " " << resB << "\n";
}
|
최대공약수, 최소공배수에 대해 알아볼 수 있는 문제였습니다.