Moscow Regional Contest 2026 · Квалификация

Задача H
Жизнь Хемингуэя

Разбор решения

Условие

Дано число s — до 10⁶ цифр.

Найти 1 ≤ l ≤ r ≤ 3·10⁵, такие что

l · (l+1) · … · r = s

s = 120 → 4 · 5 · 6 = 120

Подойдёт любой верный ответ, например и 1 · 2 · 3 · 4 · 5.

Проблема 1

Отрезков слишком много

Пар (l, r) — около 3·10⁵ · 3·10⁵ / 2 ≈ 4.5 · 10¹⁰
Даже если бы произведение на отрезке считалось за O(1), перебрать все пары не успеем

→ Будем для каждого l находить подходящий r.

Префиксные произведения

pref[i] = 1 · 2 · … · i

l·…·r = pref[r] / pref[l−1]

Пример: 4·5·6 = 720 / 6 = 120

Деление превращаем в поиск

pref[r] / pref[l−1] = s

⇕

pref[r] = s · pref[l−1]

Кладём все pref[r] в хэш-таблицу «значение → r»
Для каждого l считаем нужное значение и ищем его в таблице
Проверяем, что найденный r ≥ l

Перебор пар исчез: один проход по l.

Как это работает: s = 210

Проблема 2

Но так тоже не зайдёт

pref[300000] = 300000! — 1 512 852 цифры

В C++ длинной арифметики нет — писать самому долго
В Python она есть, но умножение и сравнение длинных чисел — не O(1), а O(длины числа)
Посчитать 3·10⁵ префиксов по ~10⁶ цифр → порядка 10¹¹ операций

Решение: работаем с остатками

Если A = B, то A % p = B % p. При большом простом p обратное почти всегда тоже верно.

s = 120 по модулю 7, по цифрам:

1 → 1

1·10 + 2 = 12 → 5

5·10 + 0 = 50 → 1

4·5·6 по модулю 7:

4 → 4

4·5 = 20 → 6

6·6 = 36 → 1

Всё решение то же самое, только s и pref хранятся по модулю p — обычными числами, и они остаются меньше p.

Какое простое число взять

Чем больше p, тем меньше шанс случайного совпадения остатков. Берём p ≈ 10¹⁸, например 10¹⁸ + 9
Произведение двух чисел до 10¹⁸ не влезает в long long → умножаем через __int128 или пишем на Python

Где взять большое простое

• Запомнить готовые: 10⁹+7, 998244353, 10¹⁸+9

• Числа вида 2ⁿ − 1 (числа Мерсенна) иногда простые: 2³¹ − 1 и 2⁶¹ − 1 — простые

Но не при любом n: 2¹¹ − 1 = 2047 = 23 · 89. Простым оно может быть, только если n простое.

Код

const long long MOD = 1000000000000000009LL;     // простое около 10^18
long long mul(long long a, long long b) { return (__int128)a * b % MOD; }

long long h = 0;                               // остаток s
for (char c : s) h = (mul(h, 10) + (c - '0')) % MOD;

pref[0] = 1;                                 // префиксные произведения
for (int i = 1; i <= MAXR; i++) pref[i] = mul(pref[i - 1], i);

unordered_map<long long, int> whereR;      // значение pref[r] -> r
for (int r = 1; r <= MAXR; r++) whereR[pref[r]] = r;

for (int l = 1; l <= MAXR; l++) {               // pref[r] = s * pref[l-1]
    auto it = whereR.find(mul(h, pref[l - 1]));
    if (it != whereR.end() && it->second >= l) {
        cout << l << " " << it->second; return 0;
    }
}

Итог

Произведение на отрезке = pref[r] / pref[l−1]
Деление заменяем поиском s · pref[l−1] в хэш-таблице
Огромные числа заменяем остатками по большому простому модулю

Сложность: O(|s| + R), где R = 3·10⁵