Aritra741's blog

[HELP] Number of non-negative solutions to a three variable Diophantine Equation
By Aritra741, history, 5 years ago, In English

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

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for pointing it out. I've updated the post.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply