Vijos 1047 — 最小公倍数 – 关浩博的个人网站

浏览量： 928

描述

给出两个正整数a,b(1<=a,b<=10^100)，求这两个数的最小公倍数。

题目链接

https://vijos.org/p/1047

输入格式

仅一行，包含两个正整数a和b, 中间以一个空格隔开

输出格式

仅包含一行，为a和b的最小公倍数lcm(a,b)

样例输入

123 321

样例输出

13161

题目分析

先使用辗转相除法求最大公约数 gcd(a,b)，然后 a * b / gcd(a, b) 就是最小公倍数。因为两个数的乘积等于它们的最大公约数(gcd)与最小公倍数(lcm)之积，即 a * b = gcd(a, b) * lcm(a, b)
C++：
这道题的数据范围很大，即使用 long long 也不行。所以应该用字符串存储数字，根据数学中的加减乘除的计算方法实现加减乘除的功能。
Java：
Java中有 BigInteger 类，可以进行大数运算。
Python：
直接运算就行了。但要注意输出的时候不要带小数点。

但是我要说一句，这并不代表 C++ 很垃圾，在算法比赛中使用 C++ 仍是比较好的选择。当然，多学习几门语言，根据具体的题目决定使用哪种语言更好。

AC代码（C++）

我太懒了，以后有空再写。

AC代码（Java）

import java.util.*;
import java.math.*;

public class Main {
    public static BigInteger gcd(BigInteger a, BigInteger b) {
        if (b.compareTo(new BigInteger("0")) == 0) {
            return a;
        }
        return gcd(b, a.mod(b));
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        BigInteger a = in.nextBigInteger(), b = in.nextBigInteger();
        System.out.println(a.multiply(b).divide(gcd(a, b)));
    }
}

AC代码（Python）

import math

a, b = map(int, input().split())
print(a * b // math.gcd(a, b))

打赏赞

描述