16
$\begingroup$

Given $n$ and $k$, find the number of pairs of integers $(a, b)$ which satisfy the conditions $n < a < k, n < b < k$ and $(ab-n)$ is divisible by $(a-n)(b-n)$. Given: $0 ≤ n ≤ 100000, \ n < k ≤ 10^{18}$.

Link to problem: http://www.codechef.com/SEPT11/problems/SHORT

  • 6
    For future reference, tagging a question both as elementary-number-theory and number-theory defeats the whole purpose of having two separate tags.2011-09-04
  • 0
    Is this some Project Euler kind of question? Can you provide the source?2011-09-05
  • 0
    This problem is taken from codechef. http://www.codechef.com/SEPT11/problems/SHORT2011-09-06
  • 1
    It might be simpler to find $a$ and $b$ where $ab|((a+n)(b+n)-n)$ or equivalently $ab|n(a+b+n-1)$.2011-09-06
  • 0
    Even in this expression,if we are going to find all pairs of (a,b) then running two loops for ($ 10^{18} * 10^{18}$ ) doesn't seem to be possible.I think there must be some theorem of mathematics which will make it easier to solve.2011-09-06
  • 0
    But the loops aren't (both) of that size. $ab|n(a+b+n-1)$ implies $ab \leq n(a+b+n-1)$ and $b|n(a+n-1)$. Assume WLOG $b \geq a$ then $a \leq n(a/b + 1 + (n-1)/b) < 3n$, and $b < 4n^2$. Yes, this is still a really big loop, but this starts the optimization.2011-09-06
  • 0
    @code_hacker can u tell where am i wrong with logic or ...any other issues like datatype of variables pastebin.com/qQHiwQWF2011-09-07

3 Answers 3