Я хочу рассчитать lcm of 2 long long integers как можно быстрее.LCM из 2 длинномерных целых чисел
Для ех а = 10^18 Ь = 10^17
я делал LCM (а, б) = A * B/НОД (а, б) для целых чисел , но для долго долго будет переполнение
Что должно быть быстрый способ вычислить его ??
У вас всегда будут проблемы с переполнением, особенно когда у вас большие взаимные числа. Но, чтобы компенсировать это немного, вы можете сделать, как советует Майкл, написав a * (b/gcd(a,b)). Поскольку gcd(a,b) является делителем как a, так и b, нет никаких проблем с неточными результатами из-за целочисленного деления.
a*b <= c
// When will a*b overflow c?
a > c/b
В вашем случае c может быть LLONG_MAX.
Почему бы не 'a * (b/gcd (a, b))'? –
Вы действительно спрашиваете: «Когда мне нужно использовать библиотеку« multiprecision »и как я могу наилучшим образом использовать« длинный длинный », чтобы избежать этих накладных расходов? Или вы в порядке с переполнением значений? – gbulmer