LCM

LCM(最小公倍数):

简单公式: lcm = a / gcd b
实用方法: gcd(ka, kb) = k
gcd(a, b)
lcm(ka, kb) = k * lcm(a, b)

c++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
输入2个正整数A,B,求A与B的最小公倍数。 

Input
2个数A,B,中间用空格隔开。(1<= A,B <= 10^9)
Output
输出A与B的最小公倍数。
Input示例
30 105
Output示例
210

题解:
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int main()
{
int a, b;

cin >> a >> b;
int m = a;
int n = b;

if (a < b)
{
int temp = a;
a = b;
b = temp;
}
int c;

while (b != 0)
{
c = a % b;
a = b;
b = c;
}
cout << (long long int)(m/a)*n << endl;
return 0;
}
---------------- The End ----------------
0%