2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Shakib Ahmed Oct 10 '13 at 8:40
  • $\begingroup$ 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. $\endgroup$ – D.W. Oct 11 '13 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.