Hello all! I found this problem on CodeChef: http://www.codechef.com/problems/PRYS09

I honestly don't know where to start. The brute force approach obviously won't work. Also, there are no solutions and editorials available probably because this is an old contest problem and remained unnoticed by the users. Please help!

Thanks!

I think it can be done with dynamic programming (to be able to count f (x) = the number of numbers up to x with the desired property, so the answer is f (R) — f (L-1)). The state is how many digits you've placed, whether or not you have already gone below x on some digit, and the current sum of cubes of digits mod m. Then you try each possible digit and get a new state for each valid digit.

Thanks for the reply mkirsche! I am not very good at DP problems so I am not sure how to start writing the code. If you don't mind, can you please write a pseudocode? Thanks a lot! :)

I tried . Got tle'd CODE

Calculate

F(l,m,r) as number of numbers with length not more thanl, such that sum of the cubes of their digits equals torby modulom. Then each query can be processed byO(sum_of_digits).Lets

d_{i}be thei-th digit of query numbernandlits length. Iterate by prefixes, for eachd<d_{i}adding to answerF(l-i- 1,m, - (sum_of_cubes_on_prefix_{i - 1}+d_{i}^{3})%m).