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.com/predownloaded/dc/3a/dc3a95cd31acc2b686bf505760140774ad84427b.png http://codeforces.com/predownloaded/49/4f/494f83b63edfc3713a93d927c2a7ad4931a0feac.png
Next time take a photo with your phone.
https://www.hackerrank.com/contests/sears-onsite/challenges/tough-puzzle
What?
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)
Thanks great help, how did you come about the initial deduction?
https://en.wikipedia.org/wiki/Arithmetic_function#Menon.27s_identity