Простоватые числа на C++
创建于:2025年1月18日
创建于:2025年1月18日
реши задачу на c++. вводятся два числа l и r. Каждое из них меньше или равно 2^100000 то есть принимать их надо как строки. Надо найти количество простоватых чисел между ними включительно. Простоватым называется число произведение цифр которого простое число. То есть числа состоящие только из единицы и простой цифры
Ниже разберём, как решить задачу пошагово, а затем приведём пример полноценной C++‑программы.
Даны два больших числа и (каждое может содержать до порядка 30 000 десятичных цифр, так как упомянуто «не превышает »). Требуется найти количество «простоватых» чисел в диапазоне включительно.
Определение «простоватого» числа.
Число называется «простоватым», если произведение его цифр есть простое число. Легко заметить, что произведение цифр будет простым тогда и только тогда, когда:
Иными словами, «простоватое» число в десятичной записи – это:
Примеры «простоватых» чисел:
Обозначим через количество «простоватых» чисел, не превосходящих . Тогда искомый результат для отрезка равен:
(Если , то считаем равным нулю.)
Пусть имеет цифр (в десятичной записи без ведущих нулей). Все «простоватые» числа, которые имеют строго меньше цифр (то есть от 1 до цифр), можно посчитать очень просто:
Следовательно, если ,
(При такой суммы нет, потому что «меньше 1 цифры» не бывает.)
Теперь надо посчитать, сколько -значных «простоватых» чисел не превосходит (где имеет цифр). Очевидно, -значное число не может начинаться с нуля, но его цифры могут быть лишь из множества . Причём ровно одна из них должна быть из , а остальные – .
Однако просто перебирать все кандидатов для ‑значного числа и сравнивать с можно, когда невелико. Но здесь может достигать десятков тысяч, что слишком большое для «в лоб» генерации и посимвольных сравнений .
Упростим себе жизнь, заметив, что:
Такую задачу удобно решать стандартной техникой «цифровой динамики» (digit DP).
Пусть имеет цифр: ( ).
Определим массив dp[pos][usedPrime][isTight]
, где:
pos
— текущая позиция (от 0 до ) при построении числа слева направо;usedPrime
∈ — сколько раз мы уже использовали «простую» цифру (0 или 1; 2 будет означать «неподходящее» состояние);isTight
∈ — признак того, ограничены ли мы текущей цифрой .isTight = 1
, мы не можем выбирать цифру больше, чем . Если isTight = 0
, можем выбирать любую разрешённую цифру (но мы и так хотим только из ).Переходы таковы:
pos
смотрим, какую цифру мы можем поставить:
isTight=1
.usedPrime
. Если он становится 2 — значит, это уже вторая простая цифра, и такое число не подходит (произведение цифр перестаёт быть простым). То есть такие варианты мы в dp
не добавляем.nextIsTight
. Он будет равен 1, если до этого мы шли «впритык» (isTight=1
) и сейчас . Иначе nextIsTight=0
.dp[pos+1][ nextUsedPrime ][ nextIsTight ]
, добавляя количество вариантов.Начальные условия:
dp[0][0][1] = 1
(ещё не выбрали ни одной цифры, не использовали простую, и пока полностью «прижаты» к верхней границе, ведь мы ничего не поставили).dp[...] = 0
в начале.Когда pos = n
, мы заканчиваем построение -значного числа. Условие «ровно одна простая цифра» эквивалентно usedPrime=1
.
Суммарное число подходящих -значных вариантов (не превышающих ) равно
Итого, общее количество для длины есть результат этой цифровой динамики.
После этого для исходных ответ будет
Ниже приведён упрощённый вариант кода на C++. Основная идея — реализовать функцию countUpTo(const string &X)
, которая возвращает количество «простоватых» чисел , и затем вернуть разницу для .
Обратите внимание:
l
(когда считаем ) должна аккуратно обрабатывать случай l = "1"
→ тогда получим "0".long long
или int64_t
) для счётчиков. Максимально возможное значение при — это порядка , что укладывается в диапазон 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; }
decString(...)
Умеет аккуратно вычитать 1 из десятичной строки.
countUpTo(X)
isTight = 1
).Основная программа
long long
. Это менее 1 МБ.Таким образом, решение работает достаточно быстро даже при до 30 000.
В коде выше показан полный рабочий пример на C++. Он и решает задачу.