校招算法笔面试 | 华为机试-求最小公倍数
题目题目链接
解题思绪
这是一个求最小公倍数的问题。最小公倍数可以通过两个数的乘积除以它们的最大公约数得到。
关键点
[*]数据范围： 1 ≤ a , b ≤ 100000 1 \leq a,b \leq 100000 1≤a,b≤100000
[*]需要先求最大公约数(GCD)
[*]最小公倍数 = a × b G C D ( a , b ) \frac{a \times b}{GCD(a,b)} GCD(a,b)a×b
代码
#include <iostream>
using namespace std;
// 求最大公约数 - 使用辗转相除法
int getGCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 求最小公倍数
int getLCM(int a, int b) {
int gcd = getGCD(a, b);
return (long long)a * b / gcd;// 注意防止溢出
}
int main() {
int a, b;
while (cin >> a >> b) {
cout << getLCM(a, b) << endl;
}
return 0;
}
import java.util.Scanner;
public class Main {
// 求最大公约数 - 使用辗转相除法
public static int getGCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 求最小公倍数
public static int getLCM(int a, int b) {
int gcd = getGCD(a, b);
return (int)((long)a * b / gcd);// 注意防止溢出
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int a = sc.nextInt();
int b = sc.nextInt();
System.out.println(getLCM(a, b));
}
}
}
def get_gcd(a, b):
# 求最大公约数 - 使用辗转相除法
while b:
a, b = b, a % b
return a
def get_lcm(a, b):
# 求最小公倍数
gcd = get_gcd(a, b)
return a * b // gcd
while True:
try:
a, b = map(int, input().split())
print(get_lcm(a, b))
except:
break
算法及复杂度
算法分析
[*] 辗转相除法求GCD：
[*]基于 a = k b + r a = kb + r a=kb+r 的原理
[*]两数的最大公约数即是较小数和余数的最大公约数
[*] 最小公倍数盘算：
[*]利用 L C M ( a , b ) ∗ G C D ( a , b ) = a ∗ b LCM(a,b) * GCD(a,b) = a * b LCM(a,b)∗GCD(a,b)=a∗b
[*]注意盘算过程中的溢出问题
复杂度分析
[*]时间复杂度： O ( log min ( a , b ) ) \mathcal{O}(\log \min(a,b)) O(logmin(a,b))
[*]空间复杂度： O ( 1 ) \mathcal{O}(1) O(1)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]