| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | awoo | 158 |
| 4 | cry | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | maroonrk | 152 |
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
Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).
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 contest
2) 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.
Thanks for pointing it out. I've updated the post.
Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).
Anyone?
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.
Great catch! Trying out all possible values will solve this problem. But I'm also interested in a general solution.