Help in a Number theory problem

help
1

Problem link: Problem - D - Codeforces
How to solve it without DP?

2

Find the power of each prime in the numbers from 1 to n. Then iterate i from 1 to n. For each prime in i the power of the prime must be strictly increasing, and should be equal to the power of the prime in i at the end. If the power is \alpha, the number of ways to arrange this prime would be \binom{\alpha + k -1}{k-1}
Multiply this for all primes in i and add it to our total answer, and you are done. This should work in O(n\pi(n) + k)

Edit: maybe even in O(n\log{\log{n}} +k) if you store the count of number of primes with power i

1 Like