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

Tough puzzle help
Автор pinku22, история, 8 лет назад, По-английски

I have attached the screenshot of the problem statement any help in coming up with the solution.

the link to the problem statement : https://www.hackerrank.com/contests/sears-onsite/challenges/tough-puzzle

http://codeforces.net/predownloaded/dc/3a/dc3a95cd31acc2b686bf505760140774ad84427b.png http://codeforces.net/predownloaded/49/4f/494f83b63edfc3713a93d927c2a7ad4931a0feac.png

  • Проголосовать: нравится
  • -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)

→ Ответить