LCM计算

Question

我为spoj中给出的计算LCM的问题编写了代码。我计算了两个数的gcd，用gcd除以两个数的乘法，给出了两个数的lcm，但它显示了错误的答案。

问题是在http://www.spoj.com/problems/WPC5I/

import java.math.BigInteger;
import java.util.Scanner;

class Lcm1 {
    public static void main(String args[]) throws Throwable {
        try {
            Scanner s = new Scanner(System.in);
            int siz = s.nextInt();
            for(int i = 0; i< siz; i++) {
                BigInteger a = s.nextBigInteger(), b = s.nextBigInteger();
                System.out.println((a.multiply(b)).divide(a.gcd(b)));
            }
        }
        catch(Exception e){}
    }
}

Answer 1

您的逻辑部分是wrong.Basically，您只是计算给定数字的lcm，但是用户要求找到最少k满足给定的condition.but，而不是k。请尝试使用n=340和m=230实际ans是1564，但是您的代码给出了7820。

注: lcm并不总是满足问题中给定条件的最小k。

提示:素数分解m，n，并尝试得到更多情况下的ans...try，您就会得到它。