# Finding number of numbers dividing n^m exactly p times

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?

## 1 Answer

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.

• Actually I have done this far easily. Now, interaction between two different prime is my problem. Look, for n=100, m=200 and for p=10, I have 312 such number. Reason is there are 4 numbers exactly for 2 for which I can get numbers that divide n^m for exactly p times. And if I choose any power for 5 less than or equal 40 than I am good to go. We can do the same for 5 and choosing free power of 2 less than or equal to 40 and there is 8 overlapping number being recalculated. To avoid the re-counting of number, I can try backtracking but the parameters and time limit are too tight. – Shakib Ahmed Oct 10 '13 at 8:40
• At this point it sounds like your question is really a math question, more so than a computer science question.... P.S. Yuval's approach is totally correct, so you might want to re-read his answer and think some more. It leads easily to a very nice solution. – D.W. Oct 11 '13 at 6:07