간단한 정수론 문제 스페셜 저지 2초 512MB
문제
두 양의 정수 A와 B가 주어진다.
A와 B에 다음의 세 가지 연산을 취할 수 있다:
- A와 B를 A와 B의 공약수로 나누어준다.
- A를 A의 약수 g로 나누고, B에 g를 곱한다.
- B를 B의 약수 g로 나누고, A에 g를 곱한다.
위의 연산을 여러 차례 한 이후, A+B의 값이 최소가 되게 하고 싶다.
A+B의 값이 최소가 되게 하는 A와 B의 최종 값을 구하여라.
입력
1번 줄 : t
2번 ~ t + 1번 줄 : Ai, Bi
- 1 ≤ t ≤ 500 (t는 테스트 케이스의 개수)
- Ai, Bi는 i번째 테스트 케이스에서의 초기 A, B 값
- 1 ≤ Ai, Bi ≤ 1,000,000,000
출력
i번째 줄에, i번째 테스트 케이스에서 A+B의 값이 최소가 되게 하는 A와 B의 최종 값을 공백으로 구분하여 출력하여라.
예제
2
4 5
4 6
1 5
2 3
A = 4, B = 5인 경우
1. A /= 2, B *= 2 => A = 2, B = 10
2. A /= 2, B /= 2 => A = 1, B = 5
A = 4, B = 6인 경우
1. A /= 2, B /= 2 => A = 2, B = 3
로그인해야 코드를 작성할 수 있어요.