Libraion's blog

[Help] Count number of integers from 1 to n can be represented as ax + by with given positive integers n,a,b and x,y must be natural numbers
By Libraion, history, 3 years ago, In English

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.

  • Vote: I like it
  • +70
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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. :)

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    correct me if im wrong but you've assume that every pair x, y that ax + by < ab — a — b is a bad.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        i read your comment and the solution is right. my bad

        → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +27 Vote: I do not like it

    "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 $.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    are you talking about this one https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply