_LNHTD_'s blog

[Help] DP Digit about the number multiplied by its digits !!
By _LNHTD_, history, 3 years ago, In English

Given $$$L,R (1 \leq L \leq R \leq 10^{18})$$$.

Count how many number $$$n=\overline{d_1d_2...d_k}$$$ that have $$$Q = n * d_1 * d_2 * \dots * d_k$$$ and $$$L \leq Q \leq R.$$$

I have done some calculation and found out that there are about $$$40000$$$ to $$$60000$$$ different possible product of digits: $$$d_1 * d_2 * \dots * d_k$$$. But I don't know any possible algorithm at all. Please help me! Thanks <3.

  • Vote: I like it
  • +46
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

This blog post might be helpful: https://codeforces.com/blog/entry/84354

TL;DR: for your problem, just store the prime factorization of the digit product in the DP state. That's it!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Wow thanks. I missed that $$$d_1 * d_2 * \dots * d_k < n$$$ so there is only about 5000 different $$$d_1 * d_2 * \dots * d_k$$$.

    → Reply