Counting Integer Solution to $\frac{a}{x-a} \in Z, \frac{b}{x-b} \in Z, x \geq 1$ in Sublinear Time

Question

Given two positive integers $a$ and $b$, I'd like to ask how many integer solutions $x > 0$ satisfy that both $\frac{a}{x-a}$ and $\frac{b}{x-b}$ are positive integers. A sublinear solution is preferred.

The straightforward linear solution (running in $O(min(a,b))$) is as follows. Notice that $-a \leq \frac{a}{x-a} \leq a$ and $-b \leq \frac{b}{x-b} \leq b$, and we can enumerate the value of the fraction $\frac{a}{x-a}$ or $\frac{b}{x-b}$ and check whether $x$ is feasible.

Answer 1

If $\frac x{x-a}$ is an integer, then so is one less, $\frac a{x-a}$, and vice versa. We see that for each positive divisor $d$ of $a$, we obtain a solution $x=a+d$. The task is thus merely to compute the number $\tau(a)$ of divisors of $a$, which can be done using the prime factorization of $a$. Trial division solves this in $O(\sqrt a)$.

---

EDIT: The original question got severely changed after posting this answer.

We may assume wlog that $a<b$. Now we are looking for $d\mid a$ such that $0<d+a-b\mid b$. So instead of counting the divisors of $a$, we now try to enumerate them (and check the second condition). This is readily done in $O(\sqrt a)$, again by trial division to find the prime powers dividing $a$ and then use these to iterate over all divisors (of which there are at most $2\sqrt a$).

Non-optimized code with $O(\sqrt a)$ time and $O(\log \log n)$ memory:

typedef vector<pair<int,int> > t_powr;

int BT(t_powr &powers, t_powr::iterator i, int a, int b, int d) {
   if (i==powers.end) return (d+a-b>0 && b%d==0)?1:0;
   int ac = 0, p=i->first, e=i->second;
   i++;
   while (e-->0) {
      ac += BT(power, i, a, b, d);
      d*=p;
   }
   return ac;
}

int count_x(int a, int b) {
   t_pwr powers;
   for (int p=2,at=a; p*p<=at; p+=(p&1)+1) {
      int e=0;
      while (at%p==0) {
         at/=p;
         e++;
      }
      if (e>0) {
         powers.push_back(pair<int,int>(p,e));
      }
   }
   if (at>1) powers.push_back(pair<int,int>(at,1));
   return BT(powers, powers.begin, a, b, 1);  
}