最小公倍数(lcm)

· · 个人记录

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数（Least Common Multiple，简写为 lcm）。

（1）求两个数的最小公倍数

对于两个数，它们的最小公倍数等于两数之积除以最大公约数

公式：

最小公倍数=两数乘积/最大公约数

int gcd(int a, int b)
{
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}

int lcm(int a, int b)
{
    int temp = a * b;
    temp = temp / gcd(a, b);
    return temp;
}

（2）求多个数的最小公倍数

我们可以先求出前两个数的最小公倍数(a)，再用这个最小公倍数(a)与下一个数求出它们的最小公倍数(b)，不断循环直到计算完所有数。

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}

int lcm(int a, int b)
{
    int temp = a * b;
    temp = temp / gcd(a, b);
    return temp;
}

int main()
{
    int a[4] = { 40,20,10,30 };         //最小公倍数：120
    int L = sizeof(a) / sizeof(int);    //L为元素个数

    int m = a[0];   //初始化最小公倍数：a[0]
    for (int i = 1; i < L; i++) //从 a[1]开始
    {       
        m = m * a[i] / gcd(m, a[i]);
    }

    cout << m;                      //输出最小公倍数：120

    return 0;
}
最后给个求多个数的最小公倍数的例题
Lowest Common Multiple Plus

求n个数的最小公倍数。

Input

输入包含多个测试实例，每个测试实例的开始是一个正整数n，然后是n个正整数。

Output

2 4 6

3 2 5 7

Sample Output

12

70

这题要考虑数据类型，我直接给了long long

AC代码：

#include<cstring>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#define QWQ puts("QWQ");
#define ll long long
#define MAXN 100010
using namespace std;

ll a[10000];

ll gcd(ll a, ll b)
{
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    ll temp = a * b;
    temp = temp / gcd(a, b);
    return temp;
}

int main()
{
    int n;
    while (cin >> n)
    {
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        ll m = a[0];
        for (int i = 1; i < n; i++)
        {
            m = m * a[i] / gcd(m, a[i]);
        }
        cout << m << endl;
    }
    return 0;
}