Auto comment: topic has been updated by Libraion (previous revision, new revision, compare).

Let d = gcd(a, b). Divide n, a and b by d. The problem is equivalent and, moreover, we have gcd(a, b) = 1. As far as I know, there was some theorem that stated that the biggest number that can't be written as ax + by with x and y both positive is ab — a — b. Every number >= ab — a — b + 1 can be written as such combination. Now we just have to count how many pairs (x, y) there are such that ax + by < ab — a — b. For a fixed x, we have: by < ab — a — b — ax <=> y < (ab — a — b — ax) / b <=> y < a — 1 — a(x + 1) / b. But ax < ab — a — b <=> x < (ab — a — b) / a <=> x < b — 1 — b / a <=> x + 1 < b — b / a. So x + 1 < b and (a, b) = 1 <=> a(x + 1) / b isn't an integer. So we can write y <= a — 1 — floor(a(x + 1) / b) — 1 = a — 2 — floor(a(x + 1) / b), for every x < b — 1 — b / a. So the answer is sum(a — 2 — floor(a(x + 1) / b)), with x from 0 to b — 2 — floor(b / a). Let m = b — 2 — floor(b / a) + 1. The answer can be written easier as: m * (a — 2) — sum(floor(ax / b)), where x is from 1 to m. But I think that sum(floor(ax / b)), with x from 1 to b is a/b * (b + 1) * b / 2 — (b — 1) * b / 2 / b = a * (b + 1) / 2 — (b — 1) / 2 = (ab + a — b + 1) / 2. (The proof is easy I will write it if needed). So sum(floor(ax / b)), with x from 1 to m is (ab + a — b + 1) / 2 — sum(floor(ax / b)), with x from m + 1 to b. But notice that b — (m + 1) is 2 or something so you can do this by hand. And I think that concludes the solution. Complexity should be O(1).

P.S.: I don't know how to use LATEX sorry and I might have missed some points. If you spot anything wrong please let me know, I tried solving this on the spot. :)