Как возвести число в степень по модулю за O(log n) (бинарное возведение) и не переполнить long long?
Нужно считать a^b mod m, где b до 10^18, а m = 10^9+7. Наивный цикл по b — это O(b), ясно что не пройдёт. Знаю про быстрое возведение в степень, но боюсь, что result * a переполнит даже long long, ведь оба множителя до 10^9. Как правильно?
2 ответа
Бинарное (быстрое) возведение основано на разложении показателя по битам: a^b = произведение a^(2^k) по выставленным битам b. На каждом шаге возводим основание в квадрат и, если текущий бит b равен 1, домножаем результат. Это O(log b) умножений по модулю.
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
Про переполнение: m = 10^9+7, значит a, res < m < 2^30. Произведение двух таких чисел < 2^60, а long long держит до ~9.2·10^18 ≈ 2^63. Значит res * a помещается в long long — переполнения нет. Главное — не забыть a %= m в начале (если a пришло большим) и приводить всё к long long, а не int.
Если же модуль больше ~3·10^9 (произведение вылезет за long long), используй __int128 для промежутка: res = (__int128)res * a % m;. Асимптотика та же — O(log b).
Частая ошибка — рекурсивная версия, которая считает binpow(a, b/2) дважды:
// ПЛОХО: O(b), экспоненциальное дерево вызовов
long long bad(long long a, long long b, long long m) {
if (b == 0) return 1;
return bad(a, b/2, m) * bad(a, b/2, m) % m; // два одинаковых вызова!
}
Нужно сохранить результат в переменную: long long h = binpow(a, b/2, m); h = h*h%m; if (b&1) h = h*a%m;. Тогда будет честный O(log b). Итеративная версия из принятого ответа от этой ошибки застрахована и обычно предпочтительнее на олимпиаде.