Given $$$n, a, b$$$ are all positive numbers $$$(1 \le a, b, n \le 10^{18})$$$.
Count how many numbers from $$$1$$$ to $$$n$$$ that can be represented as $$$a\times x + b\times y$$$ with $$$x,y \ge 0$$$ are arbitrarily non-negative integers.
I only know a $$$O(\sqrt{n})$$$ algorithm.
Thanks.
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. :)
correct me if im wrong but you've assume that every pair x, y that ax + by < ab — a — b is a bad.
I'm not sure I understand what you mean. Would you mind being more specific? I just have to count how many pairs (x, y) satisfy that condition. And you can see the comment below on why these pairs are unique.
i read your comment and the solution is right. my bad
"Now we just have to count how many pairs $$$(x, y)$$$ there are such that $$$ax + by < ab - a - b$$$"
I have just read your solution to this line. But the problem is count how many numbers can be represented, not how many pairs $$$(x,y)$$$ (As $$$2$$$ different pairs can result in the same number: $$$1\times 1 + 2\times 2 = 1\times 3 + 2\times 1=5$$$). Sorry if I missed something.
PS: You can place your math equations between $$$2$$$ Dollar sign $.
Yes you are right, but let's take 2 pairs (x, y) and (z, t). Then ax + by = az + bt <=> a(x — z) = b(t — y). But keep in mind that (a, b) = 1. So x — z = 0(mod b) and t — y = 0(mod a). But we have that ax + by < ab — a — b. So x < b and y < a. Having these we can conclude that only x = z and t = y satisfy this condition.
are you talking about this one https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem
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
This implication is incorrect. In case when $$$ab - a - b > n$$$ you've added extra solutions to the problem.
Basically, in this case you've achieved nothing because anyway you are interested in solutions which are less than
ab - a - b
.Ah you are right. I was to quick to make assumptions. Well, the solution can't be that different tho, right? Kappa.
Yes, I believe your reasoning about the uniqueness of pair is correct, and then the problem is reduced to computing number of solutions to $$$ax + by \le c$$$ which can be represented as some sum under the rational line which is well-known to be solvable in $$$\mathcal{O}(\log n)$$$.
golikovnik I'm curious about this well-known O(logn) solution, can you explain it in detail or give me some resources so I can have a look. Thank you in advance
https://codeforces.com/blog/entry/65500?#comment-496154
https://codeforces.com/blog/entry/65500?#comment-496352
Some problems:
https://judge.yosupo.jp/problem/sum_of_floor_of_linear
https://atcoder.jp/contests/arc111/tasks/arc111_e