1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – David Richerby Aug 23 '14 at 18:42
  • $\begingroup$ Of course I tried to google it. But I couldn't find any algorithm which is not obvious bruteforce. $\endgroup$ – Evgeny Savinov Aug 23 '14 at 19:16
  • $\begingroup$ 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 $\endgroup$ – HEKTO Aug 23 '14 at 19:40
  • $\begingroup$ I meant polynomial in common sense: $O(\max(len(A), len(B))^k)$ $\endgroup$ – Evgeny Savinov Aug 23 '14 at 20:26
  • 1
    $\begingroup$ I think you need to reformulate your requirements to the algorithm complexity. For example, please look here: en.wikipedia.org/wiki/Pseudo-polynomial_time $\endgroup$ – HEKTO Aug 23 '14 at 21:26
1
$\begingroup$

I've found a paper for you (however it's about more general case).

Welcome to the site!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I read it before and as far as I understood it contains only very slow algorithm. $\endgroup$ – Evgeny Savinov Aug 23 '14 at 20:25
  • 2
    $\begingroup$ Then include your analysis of the paper into your question. You need to show your own effort on this site, otherwise your question might be put on hold etc. $\endgroup$ – HEKTO Aug 23 '14 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.