Почему в задачах берут ответ по модулю 10^9+7 и какие грабли с переполнением long long при умножении?
Постоянно вижу «выведите ответ по модулю 10^9+7». Зачем вообще этот модуль и почему именно простое число? И главная боль: где меня поджидает переполнение long long при работе по модулю и как его системно избегать?
2 ответа
Модуль берут потому, что ответы в комбинаторных задачах растут экспоненциально (число путей, перестановок и т.п.) и не влезают ни в какой целый тип. Брать остаток позволяет работать с фиксированной разрядностью. Модуль 10^9+7 (и его брат 998244353) выбирают потому, что он простой — это критично: при простом m для любого a, не кратного m, существует обратный элемент, а значит можно «делить» по модулю (через малую теорему Ферма). 998244353 дополнительно удобен для NTT.
Грабли с переполнением. Базовое правило: остаток всегда < m ≈ 10^9 < 2^30. Тогда:
- Сложение
(a + b) % m— сумма< 2·10^9, влезает вlong long(и даже вunsigned int), но если складываешь много слагаемых без%— переполнишь. Бери%регулярно. - Умножение
a * b % m— произведение< 10^18 < 2^63, вlong longвлезает, но только если оба операнда —long long! Если написатьint a, b; ... a * b % m— умножение посчитается вintи переполнится. Объявляй переменныеlong longили приводи:(long long)a * b % m. - Вычитание
(a - b) % mможет дать отрицательное → пиши((a - b) % m + m) % m.
Каноничный приём — обернуть всё в функции и держать тип long long везде.
Удобно завести аккуратную обёртку, чтобы не думать про знаки и переполнение в каждой строке:
const long long MOD = 1e9 + 7;
long long add(long long a, long long b){ return (a + b) % MOD; }
long long sub(long long a, long long b){ return ((a - b) % MOD + MOD) % MOD; }
long long mul(long long a, long long b){ return a % MOD * (b % MOD) % MOD; }
Если модуль большой (например, до ~10^18), даже long long * long long переполнится — тогда умножение делай через __int128: (long long)((__int128)a * b % MOD). На олимпиадах под GCC __int128 доступен почти всегда.