반응형
https://www.acmicpc.net/problem/2436
2436번: 공약수
첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0
www.acmicpc.net
[ 문제풀이 ]
1. 최소공배수를 최대공약수로 나눈 값을 ab로 두고, ab = a x b로 나타냅니다.
2. a와 b의 최대공약수가 1인 쌍을 ans에 저장합니다.
3. 최소공약수 * (a + b)의 값이 최소인 쌍을 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<vector> using namespace std; int A, B; vector<pair<int, int>> ans; int idx; int Euclid(int B, int A) { while (B != 0) { int temp = A % B; A = B; B = temp; } return A; } int main() { scanf("%d %d", &A, &B); int temp = B / A; for (int i = 1; i*i <= temp; i++) { if (temp % i == 0) { if (Euclid(i, temp / i) == 1) { ans.push_back({ i * A, temp / i * A }); } } } int min = 987654321; for (int i = 0; i < ans.size();i++) { if (min > ans[i].first + ans[i].second) { min = ans[i].first + ans[i].second; idx = i; } } printf("%d %d", ans[idx].first, ans[idx].second); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1253번 - 좋다 (C++) (0) | 2023.04.15 |
|---|---|
| [ 백준 ] 2749번 - 피보나치 수 3 (C++) (0) | 2023.04.14 |
| [ 백준 ] 1484번 - 다이어트 (C++) (0) | 2023.04.12 |
| [ 백준 ] 20366번 - 같이 눈사람 만들래? (C++) (0) | 2023.04.11 |
| [ 백준 ] 13144번 - List of Unique Numbers (C++) (0) | 2023.04.10 |