실력키우기 공약수(C++)

2498 : 공약수

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 728 회    시도횟수: 2530 회   

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

예를 들어, 두 자연수 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

출처 : KOI 전국 2011 초2/중1/고1

?

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 48 49 50 51 52 53 54 55 56 57

/**************************************************************     Problem: 2498     User: a132034     Language: C++     Result: Success     Time:0 ms     Memory:1244 kb ****************************************************************/     #include    <stdio.h> #include    <vector> #include    <algorithm> #pragma warning (disable:4996)   std::vector<int> C; int gcd(int a, int b) {     while (a%b == 0) return b;     gcd(b, a%b); } int main() {     int A, B;     scanf("%d %d", &A, &B);       for (int i = 1; i <= sqrt(B); ++i)     {         if (B%i == 0)         {             if (i%A == 0)                 C.push_back(i);             if ((B / i) % A == 0)                 C.push_back(B / i);         }     }     std::sort(C.begin(), C.end());     int min = C[0] + C[C.size() - 1];     int X = C[0], Y = C[C.size() - 1];     for (int i = 1; i < C.size()/2; ++i)     {         if (gcd(C[C.size() - i - 1], C[i]) == A)         {             if (min > C[i] + C[C.size() - i - 1]);             {                 min = C[i] + C[C.size() - i - 1];                 X = C[i];                 Y = C[C.size() - i - 1];             }         }     }       printf("%d %d", X, Y);         return 0; }

실력키우기 몇 문제 안남았는데 다른것 풀다보니.. 정말 간만에 푸는 것 같다. 

뭔가 확실하게 맞는 해법인지 모르곘다.. 우선 생각했던 방법은 

최소공배수를 나눌 수 있는 수들 - 180일 경우 1 2 3 4 5 6 9 10 12 ... 180까지 중 최대공약수로 나누어지는 수를 저장하였다. 

sqrt를 안 쓰고 그냥 나눠지는 수를 쭉 저장해도 되고.. 

예를들어 sqrt를 안쓰면 180일 때 나누어 떨어지는 i를 전부 저장하면 되고 

sqrt를 사용하면 나누어 떨어지는 i와 몫을 다 저장해주면 된다. 

풀고나서 생각한건데 sqrt없이 다 저장해주었으면 sort할 필요도 없지 않은가 싶다.. 

6 180일 때 

6으로 나눠지면서 180을 나눌 수 있는 수를 모두 찾아낸 후 추가로 최대공약수가 6인(gcd) 수의 쌍을 골라내면 

(코드에서는 최대공약수에 따라 걸러내는 코드를 최소값 쌍을 찾을 때 사용하였다.)

6 12 18 30 36 60 90 180의 수가 남게 된다. 

중앙을 기준으로 각각의 쌍(30 36), (18,60), (12,90), (6, 180)이 정답의 후보가 될 수 있는데 이 중 가장 합이 작은 것은 30,36이므로 답은 30,36이 된다. 

분명 가장 중앙의 수가 가장 합이 작을 것 같은데... 수학적으로 증명을 못하겠다(공부해야겠다 ㅠㅠ) 그래서 그냥 for문을 돌리며 min값을 찾았다. 

답은 맞지만 아직 부족한게 많은 코드같다..