Finding when $(a-n)(b-n)|(ab-n)$

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

As mentioned above, we can use the transformation $c = a-n$, $d=b-n$ to rewrite the problem as $$ cd | (c+n)(d+n) - n = cd + n(c+d+n-1). $$ Equivalently, $$ cd | n(c+d+n-1), \quad 1 \leq c,d < k-n. $$ In particular, this implies that $cd \leq n(c+d+n-1)$ and so $$ c(d-n) \leq n(d+n-1). $$ Suppose that $d \geq (1+\sqrt{2})n$. In that case we can divide by $d - n$ and deduce that $$c \leq n \frac{d+n-1}{d-n} < n \frac{d+n}{d-n} = n \left(1 + \frac{2n}{d-n}\right) \leq (1+\sqrt{2})n. $$ So $$\min(c,d) \leq (1+\sqrt{2})n.$$

Fix some $c \leq (1+\sqrt{2})n$. For emphasis, we replace it with $C$. Rearranging, we have $$ Cd | nd + n(C+n-1) \triangleq nd + M. $$ This implies, in particular, that $d | M$. Hence it is enough to go over all factors of $M$. Since $M \approx n^2$, The average number of divisors is $2 \log n$, which is not too bad. Each of them can be tried separately.

It remains to efficiently find the factorization of all integers in the range $[n,(2+\sqrt{2})n]$. This can be done using a sieving algorithm (e.g. Eratosthenes) efficiently.

As noted in the comments, you can replace $(a,b)$ by $(a',b') = (a-n, b-n)$ and your condition then becomes $a'b' | n(a'+b'+n-1)$. I will make the replacement, and drop the primes.

$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(n-1)/b < n^2+n$, and $b < n^3 + 2n^2$.

But you only have to run the loop over $a$, you then use the fact that $b|n(a+n-1)$, factorize $n(a+n-1)$, and find all divisors $b$ in the range $[a,...k-n]$. Then for such pairs $(a,b)$ you check that they satisfy the condition $ab | n(a+b+n-1)$.

You can actually do better on the bounds of the a loop using the fact that $n(n−1)/b≤n(n−1)/a$, so $a≤2n+n(n−1)/a$. That is equivalent to $(a−n)^2≤2n^2−n$, so your loop is actually of size O(n).

Running the second loop from $[a,...,k-n]$ isn't wrong, it just takes too long. As to the implementation: 1) Generate a list of primes from 1 to $\sqrt{n}$. 2) Do trial division from this list of primes into n to get the factorization of n. 3) Create an array A of size $(1+\sqrt{2})n$. Each entry in the array should be a list of (prime, power) such that if this is in the $k$th entry of the array, $(n+k)$ is divisble by (prime) raised to (power). 4) You fill in this array by going thru the list of primes, finding the smallest number >= n that is divisible by prime^power, and incrementing by prime^power. 5) Now that you have the factorizations of n and all numbers in the range $[n,...,(2+\sqrt{2})n]$, you go thru and find divisors of $n*(n+k)$ that are greater than $k \space (= a-1)$. For each such divisor $b$, you check that $ab | n(a+b+n-1)$.

Not a solution, but something to reduce the length of the search.

Isn't it so that if $a$ and $b$ are very large in comparison to $n$, then the number $(a-n)(b-n)$ is in the same ballpark as $ab-n$? Then their quotient can't be much larger than 1, but yet it has to be an integer!!

If $n>0$, we always have $(a-n)(b-n)=ab-an-bn+n^2<ab-n^2-n^2+n^2=ab-n^2\le ab-n$. So the quotient $q=(ab-n)/((a-n)(b-n))>1$. As this is supposed to be a positive integer, we get something that we can take advantage of as follows.

Write $q(b)=(ab-n)(a-n)^{-1}(b-n)^{-1}$. Then it is easy to show that $q'(b)<0$, so $q(b)$ is a decreasing function with the limit $a/(a-n)$ as $b\to\infty$. So if $r$ is the smallest integer with the property $r>a/(a-n)$, then we get an upper bound for $b$ by solving the inequality $q(b)\ge r$. The bound reads $b\le n[r(a-n)-1]/[(r-1)a-rn]$.