0

我正在尝试使用以下公式查找数字的 LCM。Lcm = Gcd/(a*b)。这对于小数字来说工作得很好，但是对于大数字它会溢出，就像代码中显示的那样。我尝试使用 long long 作为变量类型，但仍然没有效果。如何解决溢出问题？

#include <iostream>
#include <vector>
using namespace std;

long long int LCM(int n1, int n2){

    const int size = 2;
    long long int sum;
    long long int gcd;
    long long int lcm = 0;
    vector<int> number(2);
    number[0] = n1;
    number[1] = n2;

while (true)
{
    sum = number[0] % number[1];
    gcd = number[1];
    if (sum == 0)
        break;
    number[0] = number[1];
    number[1] = sum;
}

lcm = ((n1*n2)/gcd);
return lcm;
}

int main()
{

    cout << LCM(28851538, 1183019) << endl;
    system("pause");

}
4

3 回答 3

4

有一个微不足道的改进。

你计算 (n1 * n2) / gcd。如果 n1 * n2 太大而无法放入 int，则会溢出。一个明显的变化是计算 ((long long) n1 * (long long) n2) / gcd。只要 n1 * n2 不太大而无法放入 long long 就可以了。

但是假设你想使用这个函数和 long long 参数。然后记住 gcd 是 n1 和 n2 的最大公约数。所以它是 n1 的除数和 n2 的除数。所以你计算 (n1 / gcd) * n2 或 (n2 / gcd) * n1，这将得到相同的结果。除非最终结果太大，否则不会溢出。

所以只需将return语句更改为

return (n1 / gcd) * n2;
于 2016-08-19T19:15:34.497 回答
2

既然您知道这gcd两个数均分，只需更改操作的顺序：

lcm = n1*(n2/gcd);
于 2016-08-19T19:15:48.507 回答
0 
long long int LCM(int n1, int n2)

参数是整数！

vector<int> number(2)

为什么又是 int ？

lcm = ((n1*n2)/gcd)

使用 n1/gcd * n2

于 2016-08-19T19:18:03.327 回答