НОД и НОК больших чисел: как посчитать lcm(a, b) без переполнения long long?
НОД через Евклид знаю. Но когда считаю НОК как a*b/gcd(a,b), при a, b около 10^9 произведение a*b уже под 10^18 — близко к границе long long, а если чисел в массиве много и беру НОК последовательно, то быстро переполняю. Как считать НОК надёжно?
2 ответа
Главный приём — сначала делить, потом умножать: lcm(a, b) = a / gcd(a, b) * b. Деление на НОД делается до умножения, поэтому промежуточное произведение меньше.
long long gcd(long long a, long long b){ return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b){
return a / gcd(a, b) * b; // делим РАНЬШЕ умножения
}
Это корректно, потому что a гарантированно делится на gcd(a,b), остатка нет. Евклид работает за O(log min(a,b)).
Но это не панацея: сам НОК может вырасти настолько, что не влезет в long long (НОК нескольких чисел растёт быстро). Если в задаче НОК массива может превысить ~9·10^18, есть варианты:
- считать НОК по модулю (если в задаче ответ просят по модулю) — но тогда нельзя делить на gcd напрямую, нужно держать ответ как разложение на простые;
- использовать
__int128для промежутка, если итоговый НОК всё же влезает в 128 бит; - если ответ заведомо огромен — длинная арифметика (Python/BigInteger) или хранение НОК как набора
(простое → макс. степень)по всем числам.
Удобный факт: с C++17 в <numeric> есть std::gcd и std::lcm, можно не писать руками. Но std::lcm тоже переполняется, если результат не влезает в тип — он не магический. Для НОК массива по простому модулю самый чистый способ: факторизуй каждое число, для каждого простого держи максимальную встреченную степень, в конце перемножь p^{max_deg} по модулю через быстрое возведение. Тогда переполнения нет вообще, а ответ корректен по модулю.