Переполнение ответа для больших значений
я пытаюсь найти 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");
}
Решение
Есть тривиальное улучшение.
Вы рассчитываете (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