pinku22's blog

By pinku22, history, 8 years ago, In English
  • Vote: I like it
  • -8
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Next time take a photo with your phone.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

By writing small values of n or from a well known property you can deduce that f(n) is multiplication of two functions phi(n) and number_of_divisors(n).

Since product of digits can only contain 2,3,5 or 7 as primes. Also max_powers of these primes can only be 30,19,13,11. Just iterate on i,j,k,l = power of 2,3,5 and 7 resp in product of primes. Then the problem reduces to number of numbers <=n having product of digits = 2^i*3^j*5^k*7^l = X and multiply by f(X). This can be easily solved using digits DP — g(position to generate, power of 2, power of 3, power of 5, power of 7, zero_or_not, prefix_or_not) — for details see attached code.

Code — http://ideone.com/CZTJFo

Time Complexity = O(number of distinct product of digits*4) = O(2*2*30*19*13*11)