Простоватые числа на C++

Ниже разберём, как решить задачу пошагово, а затем приведём пример полноценной C++‑программы.

Постановка задачи

Даны два больших числа $l$ и $r$ (каждое может содержать до порядка 30 000 десятичных цифр, так как упомянуто «не превышает $2^{100000}$»). Требуется найти количество «простоватых» чисел в диапазоне $[l,\,r]$ включительно.

Определение «простоватого» числа.
Число называется «простоватым», если произведение его цифр есть простое число. Легко заметить, что произведение цифр будет простым тогда и только тогда, когда:

1. Цифры числа могут быть только из набора $\{1,2,3,5,7\}$, потому что любая другая цифра (0,4,6,8,9) сделает произведение либо нулём, либо составным числом.
2. Среди цифр должна быть ровно одна «простая» цифра $\{2,3,5,7\}$. Все остальные (если есть) – это единицы ($1$), которые не влияют на произведение.

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

• Либо однозначное простое $2,3,5,7$;
• Либо любой набор из $n$ цифр ( $n\ge2$ ), где ровно в одной позиции стоит одна из цифр $\{2,3,5,7\}$, а во всех остальных позициях стоит $1$.

Примеры «простоватых» чисел:

• $2, 3, 5, 7$ (одна цифра);
• $12, 21, 13, 31, 15, 51, 17, 71, 1112, 1121, 1211, \dots$ и т.п.

Как посчитать количество «простоватых» чисел до заданной границы

Обозначим через $\text{countUpTo}(X)$ количество «простоватых» чисел, не превосходящих $X$. Тогда искомый результат для отрезка $[l,r]$ равен:

(Если $l=1$, то $\text{countUpTo}(0)$ считаем равным нулю.)

1) Подсчёт всех «простоватых» чисел меньшей разрядности

Пусть $X$ имеет $n$ цифр (в десятичной записи без ведущих нулей). Все «простоватые» числа, которые имеют строго меньше цифр (то есть от 1 до $n-1$ цифр), можно посчитать очень просто:

• Для каждого количества цифр $k$ ($1 \le k \le n-1$) «простоватых» чисел ровно $4 \times k$.
  Объяснение:
  • Нужно выбрать единственную «простую» цифру $\{2,3,5,7\}$ (всего 4 варианта).
  • Нужно выбрать позицию для этой цифры среди $k$ позиций (всего $k$ вариантов).
  • Остальные $k-1$ позиций будут заполнены единицами.

Следовательно, если $n \ge 2$,

(При $n=1$ такой суммы нет, потому что «меньше 1 цифры» не бывает.)

2) Подсчёт «простоватых» чисел ровно $n$‑значных, которые $\le X$

Теперь надо посчитать, сколько $n$-значных «простоватых» чисел не превосходит $X$ (где $X$ имеет $n$ цифр). Очевидно, $n$-значное число не может начинаться с нуля, но его цифры могут быть лишь из множества $\{1,2,3,5,7\}$. Причём ровно одна из них должна быть из $\{2,3,5,7\}$, а остальные – $1$.

Однако просто перебирать все $4 \cdot n$ кандидатов для $n$‑значного числа и сравнивать с $X$ можно, когда $n$ невелико. Но $n$ здесь может достигать десятков тысяч, что слишком большое для «в лоб» генерации и посимвольных сравнений $O(n^2)$.

Решение через «цифровую динамику» (Digit DP)

Упростим себе жизнь, заметив, что:

• Мы не рассматриваем никакие цифры, кроме $\{1,2,3,5,7\}$.
• У нас есть ограничение сверху $X$, которое мы хотим не превышать.
• Нужно учесть условие «ровно одна простая цифра».

Такую задачу удобно решать стандартной техникой «цифровой динамики» (digit DP).

1. Пусть $X$ имеет $n$ цифр: $x_0 x_1 \dots x_{n-1}$ ( $x_0 \neq 0$ ).

2. Определим массив dp[pos][usedPrime][isTight], где:

   • pos — текущая позиция (от 0 до $n$) при построении числа слева направо;
   • usedPrime ∈ $\{0,1,2\}$ — сколько раз мы уже использовали «простую» цифру (0 или 1; 2 будет означать «неподходящее» состояние);
   • isTight ∈ $\{0,1\}$ — признак того, ограничены ли мы текущей цифрой $x_{pos}$.
     Если isTight = 1, мы не можем выбирать цифру больше, чем $x_{pos}$. Если isTight = 0, можем выбирать любую разрешённую цифру (но мы и так хотим только из $\{1,2,3,5,7\}$).

3. Переходы таковы:

   • На шаге pos смотрим, какую цифру $d \in \{1,2,3,5,7\}$ мы можем поставить:
     • Она не должна быть больше $x_{pos}$, если isTight=1.
     • Если $d\in\{2,3,5,7\}$, то мы увеличиваем счётчик usedPrime. Если он становится 2 — значит, это уже вторая простая цифра, и такое число не подходит (произведение цифр перестаёт быть простым). То есть такие варианты мы в dp не добавляем.
   • Вычисляем nextIsTight. Он будет равен 1, если до этого мы шли «впритык» (isTight=1) и сейчас $d = x_{pos}$. Иначе nextIsTight=0.
   • Переходим к состоянию dp[pos+1][ nextUsedPrime ][ nextIsTight ], добавляя количество вариантов.

4. Начальные условия:

   • dp[0][0][1] = 1 (ещё не выбрали ни одной цифры, не использовали простую, и пока полностью «прижаты» к верхней границе, ведь мы ничего не поставили).
   • Все остальные dp[...] = 0 в начале.

5. Когда pos = n, мы заканчиваем построение $n$-значного числа. Условие «ровно одна простая цифра» эквивалентно usedPrime=1.
   Суммарное число подходящих $n$-значных вариантов (не превышающих $X$) равно

   $$dp[n][1][0] \;+\; dp[n][1][1].$$

6. Итого, общее количество для длины $n$ есть результат этой цифровой динамики.

Формула для $\text{countUpTo}(X)$

1. Пусть $n =$ число цифр в $X$. Если $X$ = "0" (или меньше "1"), то понятно, что «простоватых» чисел $\le 0$ нет. Возвращаем 0.
2. Считаем $$\text{CountSmallerLengths} = \sum_{k=1}^{n-1} 4k \;=\; 2 \, n \, (n-1)\quad (\text{если }n\ge 2,\text{ иначе }0).$$
3. С помощью описанной digit‑DP находим $\text{countNDigits}$ — сколько $n$‑значных «простоватых» чисел $\le X$.
4. Тогда $$\text{countUpTo}(X) \;=\; \text{CountSmallerLengths} \;+\; \text{countNDigits}.$$

После этого для исходных $l,r$ ответ будет

Полный пример решения на C++

Ниже приведён упрощённый вариант кода на C++. Основная идея — реализовать функцию countUpTo(const string &X), которая возвращает количество «простоватых» чисел $\le X$, и затем вернуть разницу для $[l,r]$.

Обратите внимание:

• Функция для вычитания 1 из строки l (когда считаем $l-1$) должна аккуратно обрабатывать случай l = "1" → тогда получим "0".
• Мы используем 64-битный тип (long long или int64_t) для счётчиков. Максимально возможное значение при $n\approx 30000$ — это порядка $1.8 \times 10^9$, что укладывается в диапазон 64-бит.
• Для ускорения (и чтобы не «держать» массив dp в три измерения) можно делать «прокат» (rolling array) по pos — т.е. держать dp только для текущего и следующего pos. Но и статический массив размером [30001][2][2] по памяти тоже вполне возможен (это около 120 000 ячеек, что не слишком много).

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

// Удобное множество "разрешённых" цифр (кроме '0', т.к. хотим именно n-значные без лидирующих нулей).
static const vector<int> ALLOWED = {1,2,3,5,7};

// Вычитаем 1 из строкового числа (предполагается, что оно > "0").
string decString(const string &s) {
    // Если s == "0", вернём "0", но будем вызывать осознанно только для s >= "1".
    // Если s == "1", то s-1 = "0".
    // Иначе обычное вычитание 1 в десятичном виде.
    if (s == "0") return "0";
    if (s == "1") return "0";

    // Алгоритм вычитания:
    // идём с конца, вычитаем 1, если получается отрицательно, занимаем у предыдущей цифры и т.д.
    string result = s;
    int i = (int)result.size() - 1;
    while (i >= 0) {
        if (result[i] == '0') {
            result[i] = '9';
            i--;
        } else {
            result[i]--;
            break;
        }
    }
    // Удалим возможные ведущие нули (но в принципе их быть не должно, кроме случая "10"-1="09").
    while (result.size() > 1 && result[0] == '0') {
        result.erase(result.begin());
    }
    return result;
}

// Подсчитываем, сколько «простоватых» чисел <= X.
long long countUpTo(const string &X) {
    // Если X <= 0, то ответ 0.
    // (Например, X == "0" или пустая — никаких положительных чисел <= 0 нет.)
    if (X == "0") {
        return 0;
    }
    // Узнаем длину X.
    int n = (int)X.size();

    // 1) Числа меньшей разрядности:
    long long smallerLengths = 0;
    if (n > 1) {
        // sum_{k=1..n-1} (4*k) = 4 * (1+2+...+(n-1)) = 4*(n-1)*n/2 = 2*n*(n-1).
        smallerLengths = 2LL * n * (n - 1);
    }

    // 2) Посчитаем кол-во n-значных «простоватых» чисел, не превышающих X, через digit DP.

    // Сначала переведём X в массив цифр (int).
    vector<int> digits(n);
    for (int i = 0; i < n; i++) {
        digits[i] = X[i] - '0'; 
    }

    // dp[pos][usedPrime][isTight]:
    //   pos       -- индекс, который заполняем (0..n)
    //   usedPrime -- сколько раз мы уже использовали "простую" цифру (0 или 1; если станет 2, недопустимо)
    //   isTight   -- флаг (0 или 1), показывающий, ограничены ли мы сверху digits[pos].
    static long long dp[30002][2][2]; 
    memset(dp, 0, sizeof(dp));

    // Начальное состояние: ещё не поставили ни одной цифры,
    // usedPrime=0, isTight=1 (т.к. пока не выбрали ничего и строго ограничены X).
    dp[0][0][1] = 1;

    for (int pos = 0; pos < n; pos++) {
        for (int usedPrime = 0; usedPrime < 2; usedPrime++) {
            for (int tight = 0; tight < 2; tight++) {
                long long ways = dp[pos][usedPrime][tight];
                if (ways == 0) continue;

                int limit = (tight ? digits[pos] : 9);
                // Перебираем разрешённые цифры d из {1,2,3,5,7}, которые <= limit
                for (int d : ALLOWED) {
                    if (d > limit) break; // так как ALLOWED отсортирован
                    int newUsedPrime = usedPrime + ((d == 1) ? 0 : 1);
                    if (newUsedPrime > 1) {
                        // означает, что получилось >= 2 простых цифр => произведение не простое
                        continue;
                    }
                    int newTight = tight && (d == limit);
                    dp[pos+1][ newUsedPrime ][ newTight ] += ways;
                }
            }
        }
    }

    // Кол-во n-значных «простоватых» чисел <= X:
    long long countNdigits = dp[n][1][0] + dp[n][1][1];

    // Итог:
    return smallerLengths + countNdigits;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string l, r;
    cin >> l >> r;

    // Функция для преобразования l-1:
    auto lMinus1 = decString(l);

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

    return 0;
}

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

1. decString(...)
   Умеет аккуратно вычитать 1 из десятичной строки.

   • Если вход равен "1", результатом будет "0".
   • Если было что-то побольше, идёт стандартное «занимание» при вычитании.

2. countUpTo(X)

   • Если $X = "0"$, сразу возвращаем 0, т.к. нет положительных чисел $\le 0$.
   • Считаем $n = X.size()$.
   • Добавляем в результат количество «простоватых» чисел меньших разрядностей (если $n>1$). Формула $4 + 8 + \dots + 4(n-1) = 4\cdot\frac{(n-1)n}{2} = 2n(n-1)$.
   • Затем запускаем «цифровую динамику» (digit DP), которая перебирает именно $n$-значные варианты (за счёт того, что первая цифра не может быть 0, а мы и не позволяем в цикле). Из множества {1,2,3,5,7} берём только те, которые $\le$ соответствующей цифре $X$ (если флаг isTight = 1).
   • В конце суммируем $\text{dp}[n][1][0]$ и $\text{dp}[n][1][1]$, то есть все способы закончить ровно с одной «простой» цифрой и при этом число не превысило $X$.

3. Основная программа

   • Считывает строки $l$ и $r$.
   • Считает $\text{countUpTo}(r) - \text{countUpTo}(l-1)$.
   • Печатает результат.

Оценка сложности

• Длина входных чисел может доходить до ~30 000 цифр.
• В нашем DP-массиве $\text{dp}[pos][usedPrime][isTight]$ будет примерно $n \times 2 \times 2 = 4n$ состояний. Для $n=30\,000$ это 120 000 состояний.
• Из каждого состояния делаем перебор по 5 «разрешённым» цифрам ($\{1,2,3,5,7\}$). Получаем порядка $600\,000$ операций, что для C++ вполне выполнимо.
• Память под DP в статическом массиве: $\sim 30001 \times 2 \times 2 \approx 120000$ ячеек long long. Это менее 1 МБ.
• Все подсчёты укладываются в 64‑бит (с запасом).

Таким образом, решение работает достаточно быстро даже при $n$ до 30 000.

Итого

1. Читаем $l$ и $r$ как строки.
2. Считаем результат как $\text{countUpTo}(r) - \text{countUpTo}(l - 1)$.
3. «Простоватые» числа — те, что содержат ровно одну простую цифру ($2,3,5,7$), а остальные $1$.
4. Подсчёт выполняем через сумму по меньшим разрядностям + «цифровую динамику» для длины, равной длине текущего $X$.

В коде выше показан полный рабочий пример на C++. Он и решает задачу.