### SPyofgame's blog

By SPyofgame, history, 9 months ago,

### 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$
Calculating x * f(x) - O(log10(x))
Counting - O(n log10(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
Building function - O(result + log10(n))

### 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 small amount of such tuples (493 tuples for $N = 10^9$ and 5914 tuples for $N = 10^{18}$)

Find all possible tuples - O(quartic_root(N))

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)$

Lets make some definition
Notice that
Ugly precalculation code - O(1)
magic function - O(18*p2*p3*p5*p7)

### About the proving stuff

1) $\forall x \in \mathbb{N}, f(x) \leq x$

• Proof: $x = \overline{\dots dcba} = \dots + d \times 10^3 + c \times 10^2 + b \times 10^1 + a \times 10^0 \geq \dots \times d \times c \times b \times a = f(x)$

2) If $x$ satisfy then $f(x) \leq \sqrt{N}$ must be satisfied

• Proof: $x \times f(x) \leq N \Rightarrow f(x) \times f(x) \leq N \Rightarrow f(x) \leq \sqrt{N}$

3) $\exists\ a, b, c, d \in \mathbb{N} \rightarrow f(x) = 2^a \times 3^b \times 5^c \times 7^d$

• Since $x = \overline{\dots dcba} \Rightarrow (0 \leq \dots, d, c, b, a \leq 9)$ and $f(x) = \dots \times d \times c \times b \times a$

• And we also have $\forall$ digit $v$ ($v \in \mathbb{N}, 0 \leq v \leq 9$) $\rightarrow \exists\ a, b, c, d \in \mathbb{N} \rightarrow v = 2^a \times 3^b \times 5^c \times 7^d$

• And because $f(x)$ is the product of digits of $x$, hence the statement is correct

4) If we know $f(x)$ we can find such $x$ satisfy $x \in [L, R]$

• Proof: Since $f(x)$ is created from factors of digits of $x$, so $x$ can also be generated using the factors

5) Number of tuples $(a, b, c, d)$ satisfy $P = 2^a \times 3^b \times 5^c \times 7^d \leq \sqrt{N}$ is very small

• Lets $O(k(x)) = O(log_2(x) \times log_3(x) \times log_5(x) \times log_7(x))$

• Since each value $x$ have the upper bound of $log_x(\sqrt{N})$. So the complexity is about $O(log_2(\sqrt{N}) \times log_3(\sqrt{N}) \times log_5(\sqrt{N}) \times log_7(\sqrt{N})) = O(k(\sqrt{N})) \leq O(log_2(\sqrt{N})^4)$

• But actually for $R \leq 10^{18}$, the complexity is just about $O(k(\sqrt[4]{N}))$

Weak proof - N = 10^k
Weak proof - N = 2^k
Code

### About the complexity:

• $O(h(x)) = O(log_{10}(N))$ is number of digits we have to build
• $O(k(x)) = O(log_2(N) \times log_3(N) \times log_5(N) \times log_7(N)) = O(log(N)^4)$ is product of all prime digits $p$ with its maximum power $k$ satisfy $p^k \leq N$
• $O(g(x)) = O(k(\sqrt{N}))$ is number of such valid tuples, but for $1 \leq N \leq 10^{18}$ it is about $\approx O(k(\sqrt[4]{N})) \leq O(log_2^4{\sqrt[4]{N}})$
• The space complexity is $O(SPACE) = O(h(x) \times k(x)) = O(log_2(N) \times log_3(N) \times log_5(N) \times log_7(N) \times log_{10}(N)) = O(log(N)^5)$
• The time complexity is

Unable to parse markup [type=CF_MATHJAX]

### Other

• About the real complexity for $O(k(x))$, do you find a better/closer upper bound of counting such tuples of $(a, b, c, d \in \mathbb{N})$ that $P = 2^a \times 3^b \times 5^c \times 7^d \leq N$ ? Since my $O(log_2(N))$ complexity seem very far than the real counting and $O(log_2(\sqrt{N}))$ is closer but just correct for $N \leq 10^{18}$

• Thanks for reading and sorry for updating this blog publicly so many times (most is for the proving path and correcting the complexity)

• +63

 » 9 months ago, # |   0 Not really sure, but isnt that f(x)
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Yes your way is correct ^^, thank sir. I have just got accepted from the problem and I am writting the solution
 » 9 months ago, # |   0 I have just done the problem and wrote the solution, thanks for reading ^^If you have a better explaination/implementation or better complexity, please comment in this post too ^^.
 » 9 months ago, # | ← Rev. 3 →   +5 By the way, if you guys are interesting, here is the Vietnamese version of the problem where we need to count such valid numbers in range $[A..B]$ where $1 \leq A \leq B \leq 10^{18}$. And here is the Editorial in Vietnamese
 » 9 months ago, # |   +8 Wow, that's an amazing problem
•  » » 9 months ago, # ^ |   0 That's your problem...
•  » » » 9 months ago, # ^ |   +5 No, that's just the same name