Count the number of integer solutions to $(ax+b)/(cx+d) \in Z$

Question

Given four integers $a$, $b$, $c$, $d$ and an upper bound $N$, how to efficiently count the number of $1 \leq x \leq N$ satisfying that $\frac{ax+b}{cx+d}$ is an integer? A sublinear algorithm better than enumerating all $x$ is preferred.

Answer 1

Why, ${ax+b\over cx+d}={1\over c}{acx+bc\over cx+d}={1\over c}\left(a+{bc-ad\over cx+d}\right)$, and $bc-ad$ has only so many integer divisors. Run through them all, and you'll be fine.