GCD and LCM
InterviewTime limit2sMemory limit512 MB
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 and is their greatest common divisor, that is, the largest number such that is divisible by and is divisible by . For example, . The LCM of two integers and is their least common multiple, that is, the smallest number such that is divisible by and is divisible by . For example, .
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 and , how close to each other can two numbers be if they have the same GCD and LCM?
Given two numbers and , find numbers and such that , , and their difference is minimal.
Input
The first line of the input file contains two positive integers and ().
Output
Output two positive integers and () such that , , and their difference is minimal.