Loading [MathJax]/jax/output/CommonHTML/jax.js
본문 바로가기

문제풀이/백준

백준 2436번 공약수

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