### Aritra741's blog

By Aritra741, history, 4 weeks ago, ,

The problem is the following one:

Given an equation ax+by+cz=d, where a,b,c,d<=1e8 , find the number of non-negative integer solutions to this equation.

It will be very helpful if you provide me with an approach to solve this problem.

Problem source: UVA 12775

• +11

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).
 » 4 weeks ago, # |   +10 I think you should give source of your problem instead of explaining it yourself.It helps with two things:1) Verifying that it is not from an ongoing contest2) You have not missed out anything / omitted anything, thinking it might be useless, when it is not.One very basic thing is, you probably want non negative integer solutions for x,y,z.
•  » » 4 weeks ago, # ^ |   0 Thanks for pointing it out. I've updated the post.
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Anyone?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 I think you missed out something important: $C / gcd(A,B,C) \geq 200 \Rightarrow C \geq 200$. Since $Cz \leq D$, that means that $z \leq \frac{D}{C} \leq \frac{D}{200}$. Therefore, you can try all possible values of $z$ (from $0$ to $\frac{D}{200}$), and for each value of $z$, you can calculate the number of solutions of $Ax+By = D-Cz$.I'm still interested in the solution for the general case of the problem. Using generating functions, I know that the number of solutions should be the coefficient of $x^D$ in $(\sum_{i=0}^\infty x^{Ai})(\sum_{i=0}^\infty x^{Bi})(\sum_{i=0}^\infty x^{Ci}) = \frac{1}{(1-x^{Ai})(1-x^{Bi})(1-x^{Ci})}$, but I'm unable to find a closed-form formula for that coefficient.
•  » » » 4 weeks ago, # ^ |   0 Great catch! Trying out all possible values will solve this problem. But I'm also interested in a general solution.