Блог пользователя Aritra741

Автор Aritra741, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится +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 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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Aritra741 (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone?

  • »
    »
    5 лет назад, # ^ |
    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Great catch! Trying out all possible values will solve this problem. But I'm also interested in a general solution.