Переполнение ответа для больших значений

Я пытаюсь найти 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");

}

3 ответа

Есть тривиальное улучшение.

Вы рассчитываете (n1 * n2) / gcd. Это переполнится, если n1 * n2 слишком велик, чтобы поместиться в int. Одним очевидным изменением будет вычисление ((длинный длинный) n1 * (длинный длинный) n2) / gcd. Это хорошо, если n1 * n2 не слишком велик, чтобы вписываться в long long.

Но предположим, что вы хотите использовать эту функцию с длинными длинными аргументами. Затем помните, что gcd - это наибольший общий делитель n1 и n2. Так что это делитель n1 и делитель n2. Таким образом, вы рассчитываете (n1 / gcd) * n2 или (n2 / gcd) * n1, что даст тот же результат. Не будет переполнения, если конечный результат не будет слишком большим.

Так что просто измените оператор возврата на

return (n1 / gcd) * n2; 

Так как вы знаете, что gcd делит поровну на оба числа, просто меняя порядок операций:

lcm = n1*(n2/gcd);
long long int LCM(int n1, int n2)

параметры являются целыми!

vector<int> number(2)

почему опять инт?

lcm = ((n1*n2)/gcd)

используйте n1/gcd * n2

Другие вопросы по тегам