GCD & LCM Inverse (POJ 2429)

Given greatest common divisor and least common multiple, you are asked to find the origin two integers and let the difference between the two is as small as possible.

Assume the two origin number is and , then we have , but . In fact we have . Let , then there must have

While and are divisor of and and they are relatively-prime with each other. So we first get to get the multiplication of and , then we start from to iterately find for and thus we get . We stop iteration when the first time we find a pair and that are relatively-prime. Then we return and .

import java.io.*;
import java.util.*;

public class GCDLCMInverse {
private static long gcd(long a, long b) {
if (b == 0) return a;
else return gcd(b, a % b);
}

public static void main(String[] args) throws IOException {
String s;
String[] str;

while ((s = in.readLine()) != null && !s.isEmpty()) {
str = s.split(" ");
long M = Long.parseLong(str[0]), N = Long.parseLong(str[1]);

N /= M;

long a = 1;

for (long i = (long)Math.sqrt(N); i >= 1; i--) {
if (N % i == 0 && gcd(i, N / i) == 1) {
a = i;
break;
}
}
System.out.printf("%d %d\n", a * M, (N / a) * M);
}
}
}