# Number of nonnegative solutions of linear Diophantine inequality

Given inequality $Ax + By \le C$, where $A, B, C$ are integers, $A$ and $B$ are coprime and $C < AB$. I need to find number of non-negative integer solutions of it.

Is there exists algorithm which run in polynomial time? For example if $A \le 10^{10}, B \le 10^{10}$ it should work less than a second. Thanks in advance.

• Googling for "counting solutions to linear inequality" gives lots of hits that look relevant: did you look at them? What have you tried? Where did you get stuck? – David Richerby Aug 23 '14 at 18:42
• Of course I tried to google it. But I couldn't find any algorithm which is not obvious bruteforce. – Evgeny Savinov Aug 23 '14 at 19:16
• You are saying "polynomial time" - do you mean $O((number of solutions)^k)$ for some constant k? The obvious brute-force algorithm is polynomial-time in this sense – HEKTO Aug 23 '14 at 19:40
• I meant polynomial in common sense: $O(\max(len(A), len(B))^k)$ – Evgeny Savinov Aug 23 '14 at 20:26
• I think you need to reformulate your requirements to the algorithm complexity. For example, please look here: en.wikipedia.org/wiki/Pseudo-polynomial_time – HEKTO Aug 23 '14 at 21:26