https://www.acmicpc.net/problem/2436
문제
> 어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.
> 예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.
> 이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다.
> 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다.
> 예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다.
> 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.
> 두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오. 접근
문제에서 최대공약수(A)와 최소공배수(B)를 줬으니 유클리드 호제법의 몇가지 개념을 생각할 수 있다.
최대 공약수는 gcd(i, j)이고 최소 공배수는 ixj를 최대공약수로 나눈 수이다. 즉, ixj=AxB이다.
그리고 최대 공약수가 A라는 말은 어떤 두 수는 적어도 약수로 A를 가진다는 뜻이다. 즉, 두 자연수는 A의 배수이므로 A의 배수들을 순회하며 쌍을 찾으면 된다.
근데 A와 B의 곱을 i로 나누어서 j를 찾고있으므로 이는 다시말하면
AXB의 약수 쌍을 찾는 것과 같다. 따라서 약수는 어떤 수의 제곱수를 기준으로 대칭반복되므로 탐색중인 수의 제곱이 AXB보다 작거나 같은 수 까지만 보면된다.
예시로 쭉 구해보면 A가 6 B가 180일때, i를 6부터 6의 배수를 보면 i가 42일때, 180이 나누어 떨어지지 않아 j가 소수점이 나온다.
따라서 이런 예외를 위해 Axb % i 가 0일 때만 봐줌으로서 탐색 범위를 줄인다.
이제 두 수를 구했으면 또 한가지 봐야할게 있다. 이 두 수를 통해서 gcd연산을 했을 때 정말 최대공약수가 A가 나오냐이다.
예를 들어 A가 3이고 B가 60일때 i가 6이라면 j가 30인데 둘로 gcd(6,30)을 구해보면 A가 6이나오면서 아니게 된다.
따라서 gcd(i,j)가 A가 나오는지 검증을 추가해준다.
이 과정이 끝나면 i,j의 쌍이 나오는데 각각의 쌍의 합을 비교하면서 더 작은 합의 쌍을 결과 변수에 담아놓고 갱신해주면 된다.
문제해결
> 입력으로 주어진 최대공약수 최소공배수를 A와 B로 받고 결과를 받을 result 쌍도 선언한다. 최대 최대공약수 최소공배수가 최대 100,000,000까지 이므로 long long형으로 전부 선언한다.
> i를 기준으로 i가 A일 때 부터 시작해서 i의 제곱이 AXB보다 작거나 같을 때까지 i를 A씩 증가시키면서(A의 배수) 반복을 해 j를 구한다.
> 접근에서 고려했던 예외를 전부 추가해준다. A와B의 곱이 i로 나누어 떨어지지 않을 때, 나눠떨어지는 쌍이 gcd연산을 했을 때 결과로 A값을 가지지 않을 때를 continue해서 제외해준다.
> 이제 모두 만족하면 i와 j를 가지고 먼저 가장 먼저 나온 쌍을 최소값으로 잡고 시작한다. 다음 쌍부터 첫 쌍의 합과 비교해 더 크면 결과 쌍을 갱신해주고 아니면 그대로 두며 쭉 연산해나간다.
> 최종 결과를 출력한다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long gcd(long long i, long long j)
{
if (i < j)
swap(i, j);
while (j > 0)
{
int r = i % j;
i = j;
j = r;
}
return i;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
long long A, B;
cin >> A >> B;
long long j = 0;
pair<long long, long long> result;
for (long long i = A; i * i <= A * B; i += A)
{
if (A * B % i != 0) continue;
j = A * B / i;
if (gcd(i, j) != A) continue;
if (i == A)
{
result.first = i;
result.second = j;
continue;
}
if (i + j < result.first + result.second)
{
result.first = i;
result.second = j;
}
}
cout << result.first << " " << result.second << '\n';
}
후기
알고있는 정보가 gcd(i,j)는 A이다. 와 ixj/A = B이다 뿐이었다.
이를 통해서 여러가지 조건과 예외를 도출해 나가는게 꾀 복잡했다.
시간초과가 나지않게 반복문에서 탐색하는 범위를 줄이기 위해
조건식이 결국 뭘 뜻하는지 파악해서 제곱근까지 탐색하고, 배수만 탐색하고도 쉽지않았다.
