### _LNHTD_'s blog

By _LNHTD_, history, 4 weeks ago,

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.

• +46

 » 4 weeks ago, # |   +15 This blog post might be helpful: https://codeforces.com/blog/entry/84354TL;DR: for your problem, just store the prime factorization of the digit product in the DP state. That's it!
•  » » 4 weeks ago, # ^ |   +12 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$.
•  » » » 4 weeks ago, # ^ |   0 Can you please elaborate the final solution you made after resolving