아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

최대공약수와 최소공배수

면접 대비

시간 제한2초메모리 제한512 MB

요약
두 수 a, b가 주어질 때 a, b와 최대공약수와 최소공배수가 같은 x <= y를 찾아 y - x가 최소가 되도록 한다.
난이도

보통10점 중 6점

유형
정수론, 수학, 완전 탐색, 정렬
정답자
아직 제출이 없습니다

문제

세레자는 수학 문제를 아주 좋아한다. 얼마 전 수학 동아리에서 최대공약수와 최소공배수가 무엇인지 배웠다.

두 자연수 aa와 bb의 최대공약수는 두 수의 공통 약수 중 가장 큰 수 xx, 즉 aa가 xx로 나누어떨어지고 bb도 xx로 나누어떨어지는 가장 큰 xx이다. 예를 들어 gcd⁡(24,18)=6\gcd(24, 18)=6이다. 두 정수 aa와 bb의 최소공배수는 두 수의 공통 배수 중 가장 작은 수 xx, 즉 xx가 aa로 나누어떨어지고 xx가 bb로 나누어떨어지는 가장 작은 xx이다. 예를 들어 lcm⁡(24,18)=72\operatorname{lcm}(24, 18)=72이다.

세레자는 최대공약수와 최소공배수가 같은 수 쌍이 여러 개 있을 수 있다는 것을 곧바로 알아차렸다. 이제 그는 이런 질문에 관심을 가졌다. 두 수 aa와 bb가 주어졌을 때, 최대공약수와 최소공배수가 aa와 bb의 것과 같은 두 수는 서로 얼마나 가까울 수 있을까?

두 수 aa와 bb가 주어졌을 때, gcd⁡(a,b)=gcd⁡(x,y)\gcd(a, b)=\gcd(x, y)이고 lcm⁡(a,b)=lcm⁡(x,y)\operatorname{lcm}(a, b)=\operatorname{lcm}(x, y)이며 y−xy-x가 최소인 두 수 xx와 yy를 찾아라.

입력

첫째 줄에 두 자연수 aa와 bb가 주어진다. (1≤a≤b≤1091 \le a \le b \le 10^9)

출력

gcd⁡(a,b)=gcd⁡(x,y)\gcd(a, b)=\gcd(x, y)이고 lcm⁡(a,b)=lcm⁡(x,y)\operatorname{lcm}(a, b)=\operatorname{lcm}(x, y)이며 y−xy-x가 최소인 두 자연수 xx와 yy (1≤x≤y1 \le x \le y)를 출력한다.

예제2

  1. 예제 1

    입력
    3 4
    
    예상 출력
    3 4
    
  2. 예제 2

    입력
    1 12
    
    예상 출력
    3 4