Переполнение int и long long

int вмещает числа только до 2 147 483 647 (примерно 2,1·10⁹). Если результат больше, int переполняется: ответ становится неверным, часто отрицательным, и никакого сообщения об ошибке нет. Для больших чисел берите long long — до 9 223 372 036 854 775 807 (примерно 9,2·10¹⁸).

#include <iostream>
#include <climits>
using namespace std;

int main() {
    cout << INT_MAX << "\n";
    cout << LLONG_MAX << "\n";
    return 0;
}

2147483647
9223372036854775807

Пределы есть в <climits>: INT_MAX, INT_MIN, LLONG_MAX, LLONG_MIN.

Главная ловушка: умножение

Поменять тип результата недостаточно:

int a = 100000, b = 300000;
long long c = a * b;        // неверно!

a * b считается в типе int, потому что оба множителя — int. Произведение переполняется до того, как попадёт в long long. Нужно, чтобы хотя бы один множитель был long long уже при умножении:

#include <iostream>
using namespace std;

int main() {
    int a = 100000, b = 300000;
    long long c = 1LL * a * b;
    long long d = (long long)a * b;
    cout << c << " " << d << "\n";
    return 0;
}

30000000000 30000000000

1LL — единица типа long long; умножение на неё переводит всё выражение в long long. Порядок важен: a * b * 1LL не поможет, потому что a * b уже посчитано в int.

То же со сдвигами (1 << 40 — единица, сдвинутая на 40 двоичных разрядов, то есть 2⁴⁰): 1 << 40 переполняет int, а 1LL << 40 даёт 1 099 511 627 776.

Как понять, что дело в переполнении

• ответ отрицательный там, где его быть не может (сумма положительных чисел, площадь);
• на маленьких тестах решение верно, а на больших — «неправильный ответ»;
• в задаче числа до 10⁹, а их складывают или умножают.

Прикидывайте размер ответа заранее: сумма 10⁵ чисел до 10⁹ — это до 10¹⁴, нужен long long; произведение двух чисел до 10⁹ — до 10¹⁸, long long ещё хватает; произведение трёх — уже нет.

Подводные камни

• long — не то же, что long long. В Windows long занимает 4 байта, как int, а в Linux на 64-битных компьютерах — 8. Пишите long long: он везде 8 байт.
• Ввод и вывод через printf/scanf для long long — формат %lld: scanf("%lld", &x), printf("%lld\n", x). С %d значение прочитается или выведется неверно.
• Число в коде. int x = 3000000000; не помещается в int; g++ предупредит об этом (overflow in conversion), но соберёт программу с неверным значением.
• Переполнение long long тоже бывает. Если ответ больше 9·10¹⁸, задача ждёт другого подхода: остатка по модулю (как часто и сказано в условии), длинной арифметики (числа хранят по цифрам в массиве) или unsigned long long, если числа до 1,8·10¹⁹ и не бывают отрицательными.