1.3 Работа с числами¶

В задачах по спортивному программированию корректная работа с числами имеет ключевое значение. Ошибки переполнения, неточности вычислений и неправильное использование типов данных — одни из самых частых причин неверных решений.

Целые числа¶

Самый часто используемый целочисленный тип — int. Это 32-битный тип со значениями примерно от −2·10^9 до 2·10^9.

Если этого диапазона недостаточно, используется тип long long (64 бита), который хранит значения примерно от −9·10^18 до 9·10^18.

long long x = 98765432123456789LL;

Суффикс LL указывает, что литерал имеет тип long long.

Частая ошибка¶

Даже если результат сохраняется в long long, промежуточные вычисления могут выполняться в типе int.

int a = 50000;
long long b = a * a;
cout << b << "\n";  // неверный результат из‑за переполнения

Проблема в том, что выражение a * a вычисляется как int. Решение:

long long b = 1LL * a * a;

или

long long a = 50000;
long long b = a * a;

В большинстве задач long long достаточно. В некоторых компиляторах также доступен тип __int128_t, но он поддерживается не везде.

Модульная арифметика¶

Запись x mod m означает остаток от деления x на m.

Например:

23 mod 7 = 2

Во многих задачах требуется вывести ответ по модулю числа, например 10^9 + 7. Это позволяет работать с очень большими числами, не выходя за пределы стандартных типов.

Свойства остатка¶

Остаток можно брать после каждой операции:

(a + b) mod m = (a mod m + b mod m) mod m
(a − b) mod m = (a mod m − b mod m) mod m
(a · b) mod m = (a mod m · b mod m) mod m

Благодаря этому числа никогда не становятся слишком большими.

Пример: вычисление степени по модулю¶

long long result = 1;
for (int i = 0; i < n; i++) {
    result = (result * 3) % m;
}
cout << result << "\n";

Отрицательные остатки¶

В C++ остаток может быть отрицательным. Чтобы гарантировать значение в диапазоне 0…m−1:

x %= m;
if (x < 0) x += m;

Это особенно важно при операциях вычитания.

Числа с плавающей точкой¶

Обычно используются типы:

double (64 бита)
long double (более высокая точность)

Чаще всего double достаточно.

Вывод с заданной точностью¶

double x = 7.0 / 3.0;
printf("%.8f\n", x);

Это выведет число с 8 знаками после запятой.

Проблема точности¶

Некоторые числа невозможно точно представить в двоичной системе.

double x = 0.2 * 3;
printf("%.20f\n", x);

Результат может быть не ровно 0.6 из‑за погрешности округления.

Сравнение вещественных чисел¶

Нельзя напрямую сравнивать числа через ==.

Правильный способ:

if (abs(a - b) < 1e-9) {
    // считаем числа равными
}

Здесь 1e-9 — допустимая погрешность.

Важно помнить, что целые числа до 2^53 могут быть представлены точно в типе double.

Практические рекомендации¶

По умолчанию используйте long long, если возможны большие значения.
При умножении больших чисел явно приводите тип.
В задачах с большими ответами применяйте модульную арифметику.
Для вещественных чисел используйте сравнение с эпсилон.
Всегда проверяйте граничные случаи: ноль, отрицательные числа, переполнение.

Работа с числами — фундаментальный навык в алгоритмических задачах. Понимание диапазонов типов, свойств остатка и особенностей вещественных вычислений позволяет избежать множества скрытых ошибок.