java - 液晶模组计算

Question

我为 spoj 中给出的问题编写了代码来计算 LCM。我计算了 2 个数字的 gcd，并将 2 个数字的乘积除以 gcd，得到 2 个数字的 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

您的逻辑部分错误。基本上，您只是在计算给定数字的 lcm，但用户要求找到满足给定条件的最少 k。但您的并非最少 k。尝试案例 n=340 和 m=230 实际 ans 为 1564，但您的代码给出 7820。

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

提示：对 m,n 进行质数分解并尝试得到答案……再尝试几个案例，你就会得到它。