Блог пользователя pinku22

Автор pinku22, история, 8 лет назад, По-английски
  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Next time take a photo with your phone.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)