Переполнение и выбор типа

В арифметических задачах чаще всего проигрывают не из-за неправильной идеи, а из-за переполнения. Алгоритм верный, тесты на минималках проходят, а на реальных ограничениях всё разваливается — молча, без предупреждения.

В C++ переполнение знакового целого — это неопределённое поведение. Не «получится мусор», а буквально: компилятор имеет право считать, что этого не бывает, и выкидывать проверки. Поэтому и результат может отличаться на разных уровнях оптимизации.

Что куда помещается

тип	предел	запомнить как
int	$\approx 2.1 \cdot 10^9$	«чуть больше двух миллиардов»
unsigned int	$\approx 4.3 \cdot 10^9$	вдвое больше
long long	$\approx 9.2 \cdot 10^{18}$	«девять с чем-то на $10^{18}$»
unsigned long long	$\approx 1.8 \cdot 10^{19}$	вдвое больше
__int128	$\approx 1.7 \cdot 10^{38}$	расширение GCC, ввода-вывода нет

Практическое правило: если в задаче ограничение $10^9$ и где-то есть произведение — это long long. Если ограничение $10^{18}$ и есть произведение — это __int128 или взятие по модулю.

Ловушка первая: sqrt

Перебор делителей до корня хочется написать так:

for (long long i = 1; i <= sqrt(n); i++)   // так не надо

Здесь две беды сразу. sqrt вызывается на каждой итерации — это дорого. И, что хуже, он возвращает double с 53 битами мантиссы, а значит округляет.

Конкретный контрпример: для $n = 10^{18} - 1$ выражение (long long)sqrt((double)n) даёт $10^9$, хотя правильный ответ — $999999999$. Разница в единицу, и цикл сделает лишнюю итерацию — или, в задаче на проверку полного квадрата, соврёт.

Правильно так:

for (long long i = 1; i * i <= n; i++)

Никаких вещественных чисел, условие точное. Но следите за самим i * i: при $n$ до $10^{18}$ произведение доходит до $10^{18}$ и в long long ещё влезает, а вот если бы $i$ был int — нет.

Если корень действительно нужен как число, а не как граница цикла, берут sqrtl и потом поправляют результат на единицу в обе стороны:

long long s = (long long)sqrtl((long double)n);
while (s > 0 && s * s > n) s--;
while ((s + 1) * (s + 1) <= n) s++;

Ловушка вторая: порядок действий

Математически одинаковые выражения ведут себя по-разному.

a * b / gcd(a, b)   // переполняется
a / gcd(a, b) * b   // безопасно

Второе корректно, потому что $a$ гарантированно делится на НОД, — целочисленное деление здесь ничего не теряет. Первое считает произведение целиком, а оно может быть на порядки больше самого НОК.

То же в среднем арифметическом: (l + r) / 2 переполняется на больших границах, l + (r - l) / 2 — нет.

И то же в решете: for (long long j = (long long)i * i; ...) — приведение обязано стоять до умножения. Написать long long j = i * i при int i бесполезно: произведение уже посчитано в int и уже испорчено.

Ловушка третья: остаток от отрицательного

В C++ и Java % возвращает остаток со знаком делимого:

(-7) % 3   // == -1, а не 2

В Python — наоборот, результат всегда имеет знак делителя, и -7 % 3 даёт 2. Переносить формулы между языками поэтому опасно.

Стандартная нормализация в C++:

long long mod(long long x, long long m) { return ((x % m) + m) % m; }

Одного + m хватает, если x по модулю не превосходит m; в общем случае нужна именно двойная запись.

Ловушка четвёртая: накопление по модулю

Брать модуль нужно после каждого умножения, а не в конце:

result = result * base % MOD;   // да
result = result * base;         // нет, даже если потом % MOD

При $MOD \approx 10^9$ произведение двух остатков — до $10^{18}$, что влезает в long long едва-едва. Два умножения подряд без взятия модуля — уже переполнение.

Обратная ошибка: брать по модулю показатель степени. $a^{n \bmod m} \ne a^n \bmod m$. Показатель приводится по $\varphi(m)$, а не по $m$, — про это в статье про сравнения.

Почему не сделать всё long long

Соблазн понятный: объявить всё long long и не думать. Так делать не стоит, и причины не эстетические.

Память. Массив на $10^7$ элементов — 40 МБ вместо 80 МБ. Типичный лимит на олимпиаде 256 МБ, и разница решает.

Скорость. В кэш помещается вдвое меньше данных, промахов вдвое больше. На задачах с большими массивами это заметная разница по времени, иногда двукратная.

Отладка. Когда типы расставлены осмысленно, переполнение возникает там, где ты его ждёшь. Когда всё long long, оно возникает один раз — и сразу в неожиданном месте.

Разумная позиция: int по умолчанию, long long там, где действительно нужен диапазон. Пресловутый #define int long long решает проблему сегодня и создаёт её завтра.

Как ловить переполнение

При компиляции локально:

g++ -fsanitize=undefined,address -g solution.cpp -o solution

Санитайзер печатает точную строку, где знаковое переполнение произошло. Это самый дешёвый способ найти ошибку, которая иначе проявляется только на максимальном тесте.

Если нужно проверить переполнение прямо в коде, в GCC есть встроенные функции: __builtin_mul_overflow(a, b, &result) возвращает true, если произведение не поместилось.