turbozone88's blog

Digit Dp ?
By turbozone88, history, 18 months ago, In English

Calculate in $$$[L, R]$$$ how many numbers whose sum of digits and sum of squares of digits are primes ?

Limit :

  • $$$1 <= L <= R <= 10 ^ {18}$$$

  • $$$T <= 10 ^ 4$$$: is the number of queries $$$[L, R]$$$.

For example, in the $$$[1, 20]$$$ there are 4 numbers which are $$$11, 12, 14, 16$$$.

I did digit dp for each query and got TLE

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

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use memorized search to omit some useless status Such as use f[i][j][k] to indicates when number of remaining digits is i,sum of digits at now is j,sum of squares of digits at now is k 's sum of programs.

My English is not good :(

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did it for each query, and got TLE :(

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      maybe you clear array f in each query However it's not necessary

      → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.geeksforgeeks.org/find-all-numbers-between-range-l-to-r-such-that-sum-of-digit-and-sum-of-square-of-digit-is-prime/

→ Reply