[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
Difference between en1 and en2, changed 1 character(s)
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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Libraion 2021-12-14 12:38:57 1
en1 English Libraion 2021-12-14 12:35:54 413 Initial revision (published)