This page is still under construction.

Parts of this page are still being built. What you see may change.

GCD and LCM

Interview

Time limit2sMemory limit512 MB

Summary
Given a and b, find positive x <= y with the same gcd and lcm as a and b, minimizing y - x.
Level

Medium6 of 10

Topics
Number theory, Math, Brute force, Sorting
Solved
No attempts yet

Problem

Seryozha loves math problems. Recently at a math club he learned what the GCD and LCM are.

The GCD of two positive integers aa and bb is their greatest common divisor, that is, the largest number xx such that aa is divisible by xx and bb is divisible by xx. For example, gcd⁡(24,18)=6\gcd(24, 18)=6. The LCM of two integers aa and bb is their least common multiple, that is, the smallest number xx such that xx is divisible by aa and xx is divisible by bb. For example, lcm⁡(24,18)=72\operatorname{lcm}(24, 18)=72.

Seryozha immediately noticed that several pairs of numbers can have the same GCD and LCM. Now he is interested in the following question: given numbers aa and bb, how close to each other can two numbers be if they have the same GCD and LCM?

Given two numbers aa and bb, find numbers xx and yy such that 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), and their difference y−xy-x is minimal.

Input

The first line of the input file contains two positive integers aa and bb (1≤a≤b≤1091 \le a \le b \le 10^9).

Output

Output two positive integers xx and yy (1≤x≤y1 \le x \le y) such that 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), and their difference y−xy-x is minimal.

Examples2

  1. Example 1

    Input
    3 4
    
    Expected output
    3 4
    
  2. Example 2

    Input
    1 12
    
    Expected output
    3 4