首页 > 搜索 > BFS搜索 > POJ 2429 GCD & LCM Inverse [解题报告] Java
2013
11-11

POJ 2429 GCD & LCM Inverse [解题报告] Java

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树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。