Digit DP for Product of Digits

Правка en3, от vamaddur, 2017-07-13 22:52:17

Let P(x) be a function that returns the product of digits of x. For example P(935) = 9*3*5 = 135. Now let us define another function P_repeat(x):

int P_repeat(int x){
    if(x < 10) return x
    return P_repeat(P(x))
}

For a value v, find the number of numbers x less than N such that P_repeat(x) = v.

How would I make a transition between states in a digit DP for this problem?

Please help, and thanks in advance!

Теги dynamic programming, math and programming

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский vamaddur 2017-07-14 08:21:02 33 Tiny change: 'vance!\n\n' -> 'vance!\n\nUPD: The bounds are N <= 10^13.\n'
en3 Английский vamaddur 2017-07-13 22:52:17 1 Tiny change: ' value v, ind the nu' -> ' value v, find the nu'
en2 Английский vamaddur 2017-07-13 22:52:03 2 Tiny change: ' P_repeat(_x_) = v.\n\n' -> ' P_repeat(x) = v.\n\n'
en1 Английский vamaddur 2017-07-13 22:51:35 480 Initial revision (published)