Counting such number whose digit product multiple to itself smaller than given number

Правка en8, от SPyofgame, 2020-11-05 15:52:01

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$$$
Function 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 * f(x) < 1$$$. We only care about such $$$x$$$ without $$$0$$$ digit
Building function - approx O(result)

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

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

  • $$$VL, VR$$$ means the range of $$$x$$$ needed to get $$$1 \leq x \times f(x) \leq N$$$
  • Current prefix of building number is $$$X$$$
  • We $$$N$$$ digits left to build to the right of $$$X$$$
  • $$$p2, p3, p5, p7$$$ means the left factors in $$$f(x)$$$
  • $$$min(X, N) = X * 10^N$$$ means the smallest possible number with prefix $$$X$$$ and $$$N$$$ left digits
  • $$$max(X, N) = X * 10^N + 10^N - 1$$$ means the greatest possible number with prefix $$$X$$$ and $$$N$$$ left digits
  • $$$cost[v][p]$$$ means greatest divisor $$$p^k$$$ in $$$v$$$ is when $$$k = cost[v][p]$$$
  • $$$memo$$$ means current $$$x$$$ is in range $$$[VL, VR]$$$ so we can use memorization
  • $$$save = f[N][p2][p3][p5][p7]$$$ means dp-table the numbers of valid number $$$X$$$ with current states
  • $$$l_x$$$ means maximum $$$k$$$ that $$$x^k \leq 10^{18}$$$. Where $$$l2, l3, l5, l7, l10$$$ are such those numbers
  • $$$pw10[x] = 10^x$$$

Notice that

  • Initially, $$$X = 0$$$, $$$N = 18$$$, $$$(p2, p3, p5, p7)$$$ is such tuple generated by above function
  • $$$X = 0$$$ means it is not build yet
  • $$$VL \leq X \leq VR$$$ means $$$1 \leq x * f(x) \leq N$$$
  • $$$N = 0$$$ means $$$X$$$ is built completely
  • $$$(p2 + p3 + p5 + p7) = 0$$$ means $$$f(x) = P$$$
  • $$$min(X) < VL$$$ means $$$x * f(x) < L$$$ always satisfy which is not desired $$$x$$$ we are considering
  • $$$max(X) > VR$$$ means $$$x * f(x) > R$$$ always satisfy which is not desired $$$x$$$ we are considering
  • Building such digit $$$v$$$ will reduce each $$$p2, p3, p5, p7$$$ by $$$cost[v][2], cost[v][3], cost[v][5], cost[v][7]$$$
  • $$$memo = false$$$ means if we take memorization here, it is not guarantee that $$$1 \leq x * f(x) \leq N$$$
  • $$$save = -1$$$ means this dp-state it is not calculated yet
Ugly precalculation code - O(1)
magic function - O(18*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 MAXN$$$, 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))$$$

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en21 Английский SPyofgame 2020-11-08 18:08:04 60
en20 Английский SPyofgame 2020-11-07 11:02:44 132 Tiny change: '\leq N$ ? \n> Since my ' -> '\leq N$ ? Since my '
en19 Английский SPyofgame 2020-11-07 10:59:37 1409 Tiny change: '4, 11$\n\n-------\n\n#### T' -> '4, 11$\n\n========\n\n#### T'
en18 Английский SPyofgame 2020-11-06 06:29:46 3554 (published)
en17 Английский SPyofgame 2020-11-06 06:02:44 2761 Tiny change: 'sqrt{R})^4 \times log_2(R)^4)$\n\n-' -> 'sqrt{R})^4)$\n\n-' (saved to drafts)
en16 Английский SPyofgame 2020-11-05 18:40:17 1012
en15 Английский SPyofgame 2020-11-05 18:39:30 3010 Tiny change: 'leq x$\n\n> $x = \ove' -> 'leq x$\n\n Proof: $x = \ove'
en14 Английский SPyofgame 2020-11-05 18:11:26 3 Tiny change: '$p^k \leq MAXN$, which ' -> '$p^k \leq N$, which '
en13 Английский SPyofgame 2020-11-05 17:56:06 40
en12 Английский SPyofgame 2020-11-05 17:53:26 43
en11 Английский SPyofgame 2020-11-05 17:42:05 84
en10 Английский SPyofgame 2020-11-05 16:44:33 16 Tiny change: ' summary="Function f(x) - O(' -> ' summary="Calculating x * f(x) - O('
en9 Английский SPyofgame 2020-11-05 15:53:37 88 Tiny change: 'uch those numbers\n- $pw10[' -> 'uch those variables we use\n- $pw10['
en8 Английский SPyofgame 2020-11-05 15:52:01 107
en7 Английский SPyofgame 2020-11-05 15:51:08 61
en6 Английский SPyofgame 2020-11-05 15:50:12 6163 Tiny change: ' build yet)\n\n> Wher' -> ' build yet\n\n> Wher' (published)
en5 Английский SPyofgame 2020-11-05 15:05:42 552 Tiny change: 'y $O(\sqrt{\sqrt{N}}' -> 'y $O(\sqrt[4]{\sqrt{N}}' (saved to drafts)
en4 Английский SPyofgame 2020-11-05 05:03:48 23
en3 Английский SPyofgame 2020-11-05 05:03:05 12
en2 Английский SPyofgame 2020-11-05 05:02:48 170 Tiny change: 'unction - O(result)' -> 'unction - approx O(result)' (published)
en1 Английский SPyofgame 2020-11-05 04:54:10 1886 Initial revision (saved to drafts)