title: Linear Diophantine equation, Extended Euclidean Algorithm
body: <p>suppose i want to find <strong>any</strong> value of x and y such that they satisfy <code>x . W + y . D = P</code></p>
  
  <p>this can be done by the following <strong>using extended euclidean algorithm</strong></p>
  
  <pre><code>int exgcd(int a, int b, int &amp;x, int &amp;y)
  {
      if (b == 0)
      {
         x = 1;
         y = 0;
         return a;
      }
      int g, xi, yi;
      g = exgcd(b, a % b, xi, yi);
      x = yi;
      y = xi - (a / b * yi);
      return g;
  }
  </code></pre>
  
  <p>but this will be just some random x and y satisfying the equation</p>
  
  <p>suppose i add an additional constraint that i want any x y z such that </p>
  
  <pre><code>x&gt;=0 y&gt;=0 z&gt;=0 and x + y + z = n
  </code></pre>
  
  <p>how can i effectively (please share code/pseudocode if possible) find all such x y and z??</p>
  
  <p>my question boils down to find any x and y (using extended euclidean algorithm) which</p>
  
  <p>1) satisfy a linear equation</p>
  
  <p>2) fall in a given range</p>
  
  <p><a href="https://codeforces.com/contest/1244/problem/C" rel="nofollow noreferrer">here is the link to the question if you want</a></p>