Finding number of numbers dividing n^m exactly p times

Question

Suppose I am given a number $n$ (less than $10^8$) and $m$ (less than $10^7$) and $p$ (less than $10^4$), I have to write a program to find number of numbers that divide $n^m$ exactly $p$ times.

Mathematically, I have to find number of distinct $x$ such that $$ n^m \equiv 0 \mod x^p \qquad\text{and}\qquad n^m \ne 0 \mod x^{p+1} $$

(From UVa Online Judge)

What approach could be better than brute force?

Answer 1

Start by factoring $n$ (you can use a table of all primes of size at most $1e4$). Now you can write $n^m = \prod_i p_i^{c_i}$. Now come up with a criterion for $x = \prod p_i^{a_i}$ to divide $n^m$ exactly $p$ times, and use this criterion to answer your question.