2013
11-11

# GCD & LCM Inverse

Given two positive integers a and b, we can easily calculate the greatest common divisor (GCD) and the least common multiple (LCM) of a and b. But what about the inverse? That is: given GCD and LCM, finding a and b.

The input contains multiple test cases, each of which contains two positive integers, the GCD and the LCM. You can assume that these two numbers are both less than 2^63.

For each test case, output a and b in ascending order. If there are multiple solutions, output the pair with smallest a + b.

3 60

12 15

//* @author:
import java.io.*;
import java.util.*;
import java.lang.Math;

public class Main
{
public static void main(String args[]) throws Exception
{
Scanner cin=new Scanner(System.in);
long a,b,c,i;
while(cin.hasNext())
{
a=cin.nextLong();
b=cin.nextLong();
c=b/a;
for(i=(long)Math.sqrt(c);i>=1;i--)
{
if(c%i==0&&GCD(i,c/i)==1)
{
System.out.println((a*i)+" "+(b/i));
break;
}
}
}
}

static long GCD(long a,long b)
{
long temp;
while(b!=0)
{
a=a%b;
temp=a;
a=b;
b=temp;
}
return a;
}

static long LCM(long a,long b)
{
return a/GCD(a,b)*b;
}
}

1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。