The problem
Lets $$$f(x) = $$$ product of digits of $$$x$$$. Example: $$$f(123) = 1 * 2 * 3 = 6$$$, $$$f(990) = 9 * 9 * 0 = 0$$$, $$$f(1) = 1$$$
The statement is, given such limitation $$$N$$$, count the number of positive $$$x$$$ that $$$1 \leq x * f(x) \leq N$$$
Example: For $$$N = 20$$$, there are 5 valid numbers $$$1, 2, 3, 4, 11$$$
The limitation
- Subtask 1: $$$N \leq 10^6$$$
- Subtask 2: $$$N \leq 10^{10}$$$
- Subtask 3: $$$N \leq 10^{14}$$$
- Subtask 4: $$$N \leq 10^{18}$$$
My approach for subtask 1
- If $$$(x > N)$$$ or $$$(f(x) > N)$$$ then $$$(x * f(x) > N)$$$. So we will only care about $$$x \leq N$$$ that $$$x * f(x) \leq N$$$
My approach for subtask 2
- If $$$x$$$ contains $$$0$$$ then $$$f(x) = 0 \Rightarrow x \times f(x) < 1$$$. We only care about such $$$x$$$ without $$$0$$$ digit
Here is the solution:
Let takes some $$$x$$$ satisfy $$$1 \leq x * f(x) \leq N$$$
We can easily prove that $$$f(x) \leq x$$$, and because $$$x * f(x) \leq N$$$, we have $$$f(x) \leq \sqrt{N}$$$ (notice that $$$x$$$ might bigger than $$$\sqrt{N}$$$)
Since $$$f(x)$$$ is product of digits of $$$x$$$, which can be obtain by such digits {$$$1, 2, \dots, 9$$$}. So $$$f(x) = 2^a \times 3^b \times 5^c \times 7^d$$$
So we can bruteforces all possible tuple of such $$$(a, b, c, d)$$$ satisfy ($$$P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{N}$$$). There are about approximately $$$O(\sqrt[4]{N})$$$ such tuples (493 for $$$N = 10^9$$$ and 5914 tuples for $$$N = 10^{18}$$$)
For each tuples, we need to counting the numbers of such $$$x$$$ that $$$1 \leq x \times f(x) \leq N$$$ and $$$f(x) = P$$$.
- We have the value $$$P$$$, so $$$\lceil \frac{1}{P} \rceil \leq x \leq \lfloor \frac{N}{P} \rfloor$$$.
- We have the value $$$f(x) = P$$$, so $$$x$$$ can be made by digits having the product exactly $$$P$$$, so we can do some DP-digit
So now we have to solve this DP-digit problem: Calculate numbers of such $$$x$$$ ($$$L \leq x \leq R$$$) whose $$$f(x) = P$$$
Solving Subproblem
We try to build each digits by digits for $$$X$$$. Because $$$X \leq N$$$, so we have to build about $$$18$$$ digits.
Lets make a recursive function $$$magic(X, N, p2, p3, p5, p7)$$$
About the complexity:
- $$$O(g(x))$$$ is number of such valid tuples, which is approximately $$$O(\sqrt[4]{N})$$$
- $$$O(h(x))$$$ is number of digits we have to build, which is $$$O(log_{10}{N})$$$
- $$$O(k(x))$$$ is product of all prime digits $$$p$$$ with its maximum power $$$k$$$ satisfy $$$p^k \leq N$$$, which is $$$O(log_2(N) \times log_3(N) \times log_5(N) \times log_7(N))$$$
- The space complexity is $$$O(SPACE) = O(h(x) \times k(x))$$$
- The time complexity is $$$O(TIME) = O(SPACE) + O(g(x)) \times k(x))$$$
