JUNGOL 실력키우기 2498 : 공약수

어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.

예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.

이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다.

예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.

두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오.

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 
첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 
입력되는 두 자연수는 2 이상 100,000,000 이하이다.

첫째 줄에는 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 하나의 
공백을 사이에 두고 출력한다.입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 
있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다. 

[Copy] 6 180

[Copy] 30 36

[Copy] 2 86486400

[Copy] 11648 14850

 

---

 

gcd * lcm = A * B 와 lcm = gcd * a * b 라는 성질을 이용하여 해결을 하고자 했는데 시간 초과로 100점이 나오질 않는군요. 다른 블로그를 참고하니 뭔가 다른 방법으로 하는 것 같은데 그 방법을 확인해서 풀어봐야 될 것 같네요. 참고로 GCD는 반복문을 이용한 유클리드 호제법을 구현하는 방법으로 바꿨는데, 재귀 함수보다는 반복문이 보통 빠르기 때문에 수정했습니다.

2017-07-11 수정)

성공 한 코드의 경우 값을 동적으로 결정하여 저장하는 것이 아니라 미리 후보군을 저장한 뒤 후보 쌍을 검사하여 최저가 되는 쌍을 출력합니다. 후보군을 만드는 것은 먼저, 이 두 값이 gcd의 배수이며 lcm의 약수라는 것을 이용하여 gcd의 배수중 lcm을 나누어 떨어지는 값들을 후보로 합니다. 그리고 이 후보가 정렬되어 있는 경우 좌우 되칭되는 위치에 있는 값들이 쌍이 되며, 이 쌍들의 합이 최소가 되는 값을 찾아 출력하면 됩니다.

 그런데 일반적으로 중간에 위치한 값의 쌍이 최소치가 되므로 중간 위치를 구해 값을 출력하는 경우 두 수의 최대 공약수가 gcd가 아닌 값이 걸러지지 않게 되므로 틀린 값을 출력하게 됩니다. 즉, 중간 값을 이용하더라도 두 수의 최대 공약수와 gcd가 동일한지는 판단해야 하겠네요.

 

#include <iostream>
 
using namespace std;
 
int GCD(int a, int b);                            //    최대 공약수를 구한다
int LCM(int a, int b);                            // 최소 공배수를 구한다.
 
int main(void)
{
    int gcd, lcm;
 
    cin >> gcd >> lcm;
    int div = lcm / gcd;                        // lcm / gcd = A * B
 
    int A, B, j;
    for (int i = 1; ; ++i)
    {
        if (div % i != 0) continue;         // 정수가 아닌 값 제외
        j = div / i;
        if (LCM(i * gcd, j * gcd) != lcm)   continue;
        if (i > j)   break;                          // i, j 값이 역전 된 경우 최소
        A = i;
        B = j;
    }
    cout << A * gcd << ' ' << B * gcd << endl;
}
 
int GCD(int a, int b)
{
    for (int i = a % b; i != 0; a = b, b = i, i = a % b);// 유클리드 호제법을 반복문으로 구현
    return b;
}
 
int LCM(int a, int b)
{
    return a / GCD(a, b)*b;
}

 

#include <iostream>
 
using namespace std;
 
int GCD(int a, int b);                          //  최대 공약수를 구한다
int LCM(int a, int b);                          // 최소 공배수를 구한다.
 
int main(void)
{
    int gcd, lcm;
 
    cin >> gcd >> lcm;
    int div = lcm / gcd;                        // lcm / gcd = A * B
 
    int A, B, j;
    for (int i = 1; ; ++i)
    {
        if (div % i != 0) continue;         // 정수가 아닌 값 제외
        j = div / i;
        if (LCM(i * gcd, j * gcd) != lcm)   continue;
        if (i > j)   break;                          // i, j 값이 역전 된 경우 최소
        A = i;
        B = j;
    }
    cout << A * gcd << ' ' << B * gcd << endl;
}
 
int GCD(int a, int b)
{
    for (int i = a % b; i != 0; a = b, b = i, i = a % b);// 유클리드 호제법을 반복문으로 구현
    return b;
}
 
int LCM(int a, int b)
{
    return a / GCD(a, b)*b;
}

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int GCD(int a, int b);                          //  최대 공약수를 구한다
 
int main(void)
{
    int gcd, lcm;
    vector<int> v;    // 후보군을 저장하기위해 동적 배열을 사용한다.(몇개일지 모르므로)
 
    cin >> gcd >> lcm;
 
    // 두 수는 gcd 와 lcm 사이의 수이며 최소 공배수가 gcd 이므로 gcd 단위로 검사한다.
    for (int i = gcd, j = lcm; i <= j; i += gcd, j -= gcd)
    {
        // 최소 공배수로 증가하므로 gcd는 만족
        // 최대 공배수를 만족하기 위해 lcm을 나눈 나머지가 0인 것만을 저장
        // 이 과정을 통해 이후 최대 공약수가 gcd와 같다면 최소 공배수가 lcm인 것을 보장
        if (lcm % i == 0)
            v.emplace_back(i);
        if (lcm % j == 0)
            v.emplace_back(j);
    }
 
    // 나온 후보군을 왼쪽과 오른쪽의 대응되는 위치에 있는 쌍으로 만들기 위해 오름 차순 정렬
    sort(v.begin(), v.end());
    int min = v[0] + v[v.size() - 1];   // 두 수를 더한 값이 최소가 되는 쌍을 선택한다.
    int X = v[0], Y = v[v.size() - 1];  // 최초 쌍을 저장 해 둔다.
    for (int i = 1; i < v.size() / 2; ++i)
    {
        // 두 수의 최대 공약수가 gcd 인지 판단
        // gcd 보다 작은 수가 최대 공약수가 되는 경우를 제거함
        if (GCD(v[v.size() - i - 1], v[i]) == gcd)
        {
            // 이전에 저장한 쌍의 합보다 현재 들어온 쌍의 합이 적은 경우 교환한다.
            if (min < v[i] + v[v.size() - i - 1])    continue;
            min = v[i] + v[v.size() - i - 1];
            X = v[i];
            Y = v[v.size() - i - 1];
        }
    }
 
    cout << X << ' ' << Y << endl;
}
 
int GCD(int a, int b)
{
    for (int i = a % b; i != 0; a = b, b = i, i = a % b);
    return b;
}

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int GCD(int a, int b);                          //  최대 공약수를 구한다
 
int main(void)
{
    int gcd, lcm;
    vector<int> v;    // 후보군을 저장하기위해 동적 배열을 사용한다.(몇개일지 모르므로)
 
    cin >> gcd >> lcm;
 
    // 두 수는 gcd 와 lcm 사이의 수이며 최소 공배수가 gcd 이므로 gcd 단위로 검사한다.
    for (int i = gcd; i <= lcm; i += gcd)
    {
        // 최소 공배수로 증가하므로 gcd는 만족
        // 최대 공배수를 만족하기 위해 lcm을 나눈 나머지가 0인 것만을 저장
        // 이 과정을 통해 이후 최대 공약수가 gcd와 같다면 최소 공배수가 lcm인 것을 보장
        if (lcm % i == 0)
            v.emplace_back(i);
    }
 
    int min = v[0] + v[v.size() - 1];   // 두 수를 더한 값이 최소가 되는 쌍을 선택한다.
    int X = v[0], Y = v[v.size() - 1];  // 최초 쌍을 저장 해 둔다.
    for (int i = 1; i < v.size() / 2; ++i)
    {
        // 두 수의 최대 공약수가 gcd 인지 판단
        // gcd 보다 작은 수가 최대 공약수가 되는 경우를 제거함
        if (GCD(v[v.size() - i - 1], v[i]) == gcd)
        {
            // 이전에 저장한 쌍의 합보다 현재 들어온 쌍의 합이 적은 경우 교환한다.
            if (min < v[i] + v[v.size() - i - 1])    continue;
            min = v[i] + v[v.size() - i - 1];
            X = v[i];
            Y = v[v.size() - i - 1];
        }
    }
 
    cout << X << ' ' << Y << endl;
}
 
int GCD(int a, int b)
{
    for (int i = a % b; i != 0; a = b, b = i, i = a % b);
    return b;
}

 

 

JUNGOL) 문제은행) 실력키우기) 공약수