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 に収まらない場合、オーバーフローします。明らかな変更の 1 つは、((long long) n1 * (long long) n2) / gcd を計算することです。n1 * n2 が 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)

パラメータはintです！

vector<int> number(2)

なぜ再び int なのですか？

lcm = ((n1*n2)/gcd)

n1/gcd * n2 を使用

于 2016-08-19T19:18:03.327 に答える