Given $a = [a_1, a_2, a_3, a_4, \ldots, a_n]$ where $a_i$ is positive integer, I need to find the number of non negative integral solutions for the equation $$a_1x_1+a_2x+_2+a_3x_3+\ldots+a_nx_n<k$$ where $k>0$.
Asked
Active
Viewed 24 times
-1
-
What is the source of this problem? Smells like a programminng question – Gareth Ma May 03 '20 at 10:38
-
If this is from a programming contest, then s/+ve/positive/g; s/-ve/negative/g please – Hagen von Eitzen May 03 '20 at 10:40
1 Answers
0
If all $a_i$ are positive (or more generally non-negative and $a_n$ is positive), then $x\mapsto a_1x+a_2x^2+\cdots +a_nx^n$ is a strictly increasing function. Then the problem amounts to finding the minimal positive integer $x$ for which this polynomial expression is $\ge k$. A simple upper bound, good enough, e.g., for a binary search, is $\lceil\sqrt[n]{\frac k{a_n}}\rceil$.
Hagen von Eitzen
- 374,180
-
Hello, do you think the OP means $xi$ as $x_i$ or $x^i$? Since he used $x1$ in his equation – Gareth Ma May 03 '20 at 10:50