题目

牛客 - 最小公倍数

求两个数的最小公倍数，两个数的最小公倍数为：能被这两个数同时整除的最小的数。

输入两个整数n,m。答案在 int 范围内

输出两个数的最小公倍数。

输入
6 4
输出
12

输入
6 5
输出
30

思路

最小公倍数，least common multiple，为 (a * b) / gcd

Java 写法：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            System.out.println(lcm(a, b));
        }
    }
    
    /**
    * 最大公约数 - gcd
    */
    public static long gcd(long a, long b) {
        if (a % b == 0) {
            return b;
        }
        return gcd(b, a % b);
    }
    
    /**
    * 最小公倍数 - lcm = （a * b）/ gcd
    */
    public static long lcm(long a, long b) {
        return (a * b) / gcd(a, b);
    }
}

python 写法：

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)


def lcm(a, b):
    return (a * b) / gcd(a, b)


while True:
    try:
        a, b = map(int, input().split())
        print(int(lcm(a, b)))
    except:
        break

总结

也有位运算法，不过记住公式就够用了，利用辗转相除法求得最大公约数后进而求最小公倍数