Подсчет простоватых чисел

Анализ задачи

Нам нужно считать количество чисел на отрезке $[l, r]$, произведение десятичных цифр которых является простым числом. Ограничение: $1 \le l \le r \le 10^{100000}$. Очевидно, что перебор всех чисел напрямую невозможен.

Однако есть важное упрощение:

Если произведение цифр числа есть простое $p$, тогда среди цифр этого числа может быть ровно одна цифра, равная $p\in\{2,3,5,7\}$, а все остальные цифры должны быть равны $1$.

Обоснование:

• Цифры 0,4,6,8,9 (а также наличие сразу двух простых цифр) делают произведение либо нулём, либо составным числом (больше не может быть простым).
• Цифра 1 не меняет произведение (она «нейтральна»).

Иными словами, «простоватое» число в десятичной записи выглядит так:

• Оно содержит ровно одну цифру из множества $\{2,3,5,7\}$.
• Все остальные его цифры равны 1.
• Цифр 0,4,6,8,9 оно не содержит вовсе.

Примеры:

• $21$ — «простоватое» (цифры $2$ и $1$, произведение $2\cdot1=2$, простое).
• $37$ — не подходит (цифры $3$ и $7$, произведение $21$, составное).

Как посчитать, сколько таких чисел в промежутке $[l, r]$

1. Любое число длины $n$, удовлетворя условию, задаётся выбором:

   • Одной позиции $i$ $(0 \le i < n)$, где стоит одна из цифр $\{2,3,5,7\}$.
   • Остальные $n-1$ позиций заполнены цифрой $1$.

   Следовательно, при фиксированной длине $n$ существует ровно $4 \times n$ подходящих чисел (4 способа выбрать «простую» цифру и $n$ способов выбрать позицию под неё).

2. Чтобы найти количество таких чисел $\le x$, можно разделить задачу на два этапа:

   • Посчитать, сколько «простоватых» чисел меньшей длины, чем длина $x$.
   • Плюс сколько «простоватых» чисел той же длины, что и $x$, при этом $\le x$ лексикографически.

3. Сумма для меньших длин:

   Пусть $L$ = количество цифр в $x$. Тогда числа длины от $1$ до $L-1$ (если $L>1$) дают

   $$\sum_{n=1}^{L-1} (4n)\;=\;4\,\frac{(L-1)L}{2}\;=\;2\,L\,(L-1).$$

   Это легко посчитать в 64-битном типе, поскольку $L \le 100000$ и $2 \times 100000 \times 99999 \approx 2\times10^{10}$, что влезает в long long.

4. Подсчёт среди чисел той же длины $L$, что и $x$:

   Пусть $x$ имеет $L$ цифр: $x[0],x[1],\dots,x[L-1]$.
   Рассмотрим «шаблон» $s$ = строка из $L$ единиц: "111...1" (длиной $L$).
   Любое «простоватое» число длины $L$ отличается от $s$ ровно в одной позиции $i$, где ставится $\{2,3,5,7\}$, а остальные — $1$.

   Чтобы определить, когда такое число $\le x$ лексикографически, достаточно быстро сравнивать с $x$. Но прямой перебор $L\cdot 4$ чисел и сравнение каждого за $O(L)$ даст $O(L^2)$ — слишком дорого для $L$ до $100000$.

   Оптимизация: сделаем всего два обхода строки $x$:

   • prefixCmp: для каждой позиции $i$ храним результат сравнения префиксов длиной $i$:
     $\;s[0..i-1]$ vs $\;x[0..i-1]$.
     Это значение может быть $\mathit{LESS} = -1$, $\mathit{EQUAL} = 0$ или $\mathit{GREATER} = +1$.
     По сути, идём слева направо и как только находим первую позицию, где $s[j]\neq x[j]$, там определяем $\mathit{LESS}$ или $\mathit{GREATER}$ и далее уже не меняем.

     Псевдокод (считаем s[i] = '1' как символ, а x[i] — цифра-символ):

     text
     prefixCmp[0] = EQUAL
     for i in [0..L-1]:
       if prefixCmp[i] != EQUAL:
         prefixCmp[i+1] = prefixCmp[i]  // уже знаем меньше/больше
       else
         if '1' < x[i]:
           prefixCmp[i+1] = LESS
         else if '1' > x[i]:
           prefixCmp[i+1] = GREATER
         else
           prefixCmp[i+1] = EQUAL

   • suffixCmp: аналогично, но сравнение суффиксов $\;s[i..L-1]$ vs $\;x[i..L-1]$.
     Идём справа налево:

     text
     suffixCmp[L] = EQUAL
     for i in [L-1..0]:
       if '1' < x[i]:
         suffixCmp[i] = LESS
       else if '1' > x[i]:
         suffixCmp[i] = GREATER
       else
         suffixCmp[i] = suffixCmp[i+1]

     Здесь тоже используем три состояния $\{-1,0,+1\}$.

   Теперь для конкретной позиции $i$ и выбранной «простой» цифры $p \in \{2,3,5,7\}$ проверяем, будет ли число

   $$y = \underbrace{111\ldots1}_{\text{до }i}\,p\,\underbrace{111\ldots1}_{\text{после }i}$$

   $\le x$. Делается это за $O(1)$:

   1. Смотрим pc = prefixCmp[i] — сравнение префикса длиной $i$:

      • Если pc == LESS, тогда $s[0..i-1] < x[0..i-1]$. Значит весь $y$ точно $\le x$ (префикс уже строго меньше).
      • Если pc == GREATER, тогда $y > x$ независимо от того, что мы поставим в $i$-й разряд.
      • Если pc == EQUAL, то префиксы совпадают, нужно смотреть разряд $i$.

   2. Сравниваем $p$ и $x[i]$:

      • Если $p < x[i]$, значит $y < x$.
      • Если $p > x[i]$, значит $y > x$.
      • Если $p = x[i]$, то нужно ещё посмотреть суффикс s[i+1..L-1] vs x[i+1..L-1], то есть sc = suffixCmp[i+1].
        • Если sc == GREATER, тогда $s[i+1..] > x[i+1..]$, значит $y>x$.
        • Иначе $y\le x$.

Таким образом, мы за $O(L)$ формируем массивы prefixCmp, suffixCmp, а потом за O(L)` (с учётом 4 простых цифр получается \(4L) считаем, сколько «просто-ватых» чисел длины $L$ не превышают $x$.

Алгоритм целиком

1. Реализуем функцию

   $$\text{countUpTo}(x) = \#\{\text{«простоватые» } \le x\}.$$
   • Если $x = 0$ (или строка "0"), возвращаем 0. (В задаче $l\ge1$, но иногда удобно подстраховаться.)
   • Пусть $L = \text{длина}(x)$.
   • Вычисляем $\text{baseCount} = \sum_{n=1}^{L-1} 4n = 2\,(L-1)\,L$ (если $L>1$, иначе 0).
   • Строим prefixCmp и suffixCmp за $O(L)$.
   • Делаем цикл for i in [0..L-1], внутри перебираем $p \in \{2,3,5,7\}$, с помощью уже описанного сравнения проверяем $\le x$. Суммируем количество успехов в countLenL.
   • Итог: $\text{return} = \text{baseCount} + \text{countLenL}$.

2. Ответ на исходный запрос $\;[l,r]$:

   $$\#\{\text{«простоватые» } \in [l,r]\} \;=\; \text{countUpTo}(r)\;-\;\text{countUpTo}(l-1).$$

   (Причём $l>1$ означает, что $l-1 \ge1$; если $l=1$, то $\text{countUpTo}(0)=0$.)

3. Вся арифметика — в 64-битном типе (long long), так как максимальное значение, которое мы можем получить, порядка $2\cdot 10^{10}$, что не превосходит предел long long.

Ниже приведён примерный код на C++ (с комментариями).

cpp
#include <bits/stdc++.h>
using namespace std;

// Будем использовать tri-state для сравнения префиксов/суффиксов
enum CompareState { LESS = -1, EQUAL = 0, GREATER = 1 };

// Вычисляет количество "простоватых" чисел, не превосходящих x (x >= 1).
long long countUpTo(const string &x) {
    // Если x == "0" или пуста — нет подходящих чисел
    if (x == "0") return 0;

    int L = (int)x.size();
    // Считаем, сколько простоватых чисел имеют длину < L:
    // sum_{n=1}^{L-1} (4*n) = 4 * (1 + ... + (L-1)) = 4 * (L-1)*L/2 = 2*(L-1)*L
    long long baseCount = 0;
    if (L > 1) {
        long long LL = L; // чтобы умножения шли в 64-битном типе
        baseCount = 2LL * (LL - 1LL) * LL; 
    }

    // Построим prefixCmp и suffixCmp
    vector<CompareState> prefixCmp(L+1), suffixCmp(L+1);

    // prefixCmp[0] - сравнение "префикса длины 0" -> EQUAL
    prefixCmp[0] = EQUAL;
    for (int i = 0; i < L; i++) {
        if (prefixCmp[i] != EQUAL) {
            // уже знаем, что меньше или больше, состояние не меняется
            prefixCmp[i+1] = prefixCmp[i];
        } else {
            // сравниваем '1' и x[i]
            char c = x[i]; // цифра
            if ('1' < c)
                prefixCmp[i+1] = LESS;
            else if ('1' > c)
                prefixCmp[i+1] = GREATER;
            else
                prefixCmp[i+1] = EQUAL;
        }
    }

    // suffixCmp[L] - сравнение "суффикса длины 0" -> EQUAL
    suffixCmp[L] = EQUAL;
    for (int i = L - 1; i >= 0; i--) {
        char c = x[i];
        if ('1' < c)
            suffixCmp[i] = LESS;
        else if ('1' > c)
            suffixCmp[i] = GREATER;
        else
            suffixCmp[i] = suffixCmp[i + 1];
    }

    // Теперь подсчитаем, сколько чисел той же длины L <= x
    long long countLenL = 0;
    static int primes[4] = {2,3,5,7};

    for (int i = 0; i < L; i++) {
        CompareState pc = prefixCmp[i];     // сравнение префикса до i
        CompareState sc = suffixCmp[i+1];   // сравнение суффикса после i

        for (int p: primes) {
            // Решаем, <= x ?
            if (pc == LESS) {
                // префикс уже строго меньше, значит всё число заведомо <= x
                countLenL++;
            }
            else if (pc == GREATER) {
                // префикс строго больше, значит число > x
                // ничего не добавляем
            }
            else { 
                // pc == EQUAL -> префикс совпадает, надо смотреть разряд i
                int digitX = x[i] - '0';
                if (p < digitX) {
                    countLenL++;
                }
                else if (p > digitX) {
                    // y > x
                }
                else {
                    // p == digitX -> сравниваем суффиксы
                    // если sufixCmp == GREATER => s[i+1..] > x[i+1..], значит y>x
                    // иначе y<=x
                    if (sc != GREATER) {
                        countLenL++;
                    }
                }
            }
        }
    }

    return baseCount + countLenL;
}

// Основная функция решения
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string l, r;
    cin >> l >> r;
    // Считаем countUpTo(r) - countUpTo(l-1).
    // Нужно аккуратно вычислить l-1 (как строку).
    // Но если l="1", то l-1 = 0, просто подадим "0".

    // Функция для вычитания 1 из десятичной строки:
    auto decString = [&](string s){
        // Вычитаем 1 из s (s >= "1"), результат может стать "0".
        int i = (int)s.size() - 1;
        while(i >= 0 && s[i] == '0'){
            s[i] = '9';
            i--;
        }
        if(i >= 0){
            s[i]--;
        }
        // Удалим ведущие нули (если вдруг возникли) — 
        // но теоретически может остаться только "0".
        while(s.size() > 1 && s[0] == '0') {
            s.erase(s.begin());
        }
        return s;
    };

    string lminus1;
    if(l == "1"){
        lminus1 = "0";  // чтобы countUpTo("0") вернул 0
    } else {
        lminus1 = decString(l);
    }

    long long ans = countUpTo(r) - countUpTo(lminus1);
    cout << ans << "\n";

    return 0;
}

Пояснения к коду

1. Функция countUpTo(x):

   • Если входная строка x == "0", сразу возвращаем 0.
   • Сохраняем $\text{length}(x)$ в L.
   • Считаем вклад от всех чисел меньших длины: $\sum_{n=1}^{L-1} 4n = 2\,L\,(L-1)$.
   • Строим массивы prefixCmp и suffixCmp, которые за $O(L)$ дают нам информацию о лексикографических отношениях «строка из L единиц» vs x по префиксам и суффиксам.
   • Перебираем позиции $i=0..L-1$ и простые цифры $p\in\{2,3,5,7\}$. По готовой информации из prefixCmp/suffixCmp решаем за $O(1)$, будет ли число с одной «простой» цифрой в позиции i $\le x$.
   • Суммируем такие случаи.

2. Вычитание 1 из строки l:
   Нужно аккуратно обрабатывать случаи вида "1000" -> "999". Если $l$ равно "1", то $l-1 = "0"$ (оттуда мы получаем 0 в итоге).

3. Итог:

   $$\text{answer} = \text{countUpTo}(r) - \text{countUpTo}(l - 1).$$

Это полностью решает задачу за $O(|r| + |l|)$, что укладывается в требуемые ограничения даже при длине до $10^5$ цифр.