This is a well-known method to solve linear equations with 2 or more variables. The specialty of this method is that it provides integer solutions to the linear equation of the form **a*x + b*y + c*z + ……… = constant**.

The problems involving use of LDE generally deal with two variables. We gonna look at few interesting problems today :

### Problem – 01 D. Two Arithmetic Progressions

Problem Link – https://codeforces.com/contest/710/problem/D

The problem is about finding the number of possible values of x.

Here x must hold –

**a1*k’ + b1 = a2*l’ + b2 **

**a1*k’ – a2*l’ = b2-b1**

These can be treated as LDE – **A*x + B*y = C** where **x = k’** and **y = l’**. The only restriction that we have is that* a1*x + b1 must be between L and R (inclusive) and x,y must be >= 0*.

Now, we know that the solutions to this equation exist only if **C%gcd(A,B) = 0**, and that the solutions are:

**x = x’ + B*t/gcd(A,B) **and **y = y’ – A*t/gcd(A,B)** where (x’,y’) are solutions of extended euclead’s algorithm **Ax + By = gcd(A,B)** multiplied by C/gcd(A,B)

//Extended GCD starts here ll solx,soly,GCD; void extended_version(ll a, ll b){ // Base Case if (b==0){ solx=1,soly=0,GCD=a; return; } //Recursive Case extended_version(b,a%b); ll x1 = solx, y1 = soly; solx = y1; soly = x1 - (a/b)*y1; } //Extended GCD ends here

And, now we will look at the solution to original problem

ll solx,soly,GCD; void extended_gcd(ll a, ll b){ // Base Case if (b==0){ solx=1,soly=0,GCD=a; return; } //Recursive Case extended_gcd(b,a%b); ll x1 = solx, y1 = soly; solx = y1; soly = x1 - (a/b)*y1; } void solve() { ll a1,b1,a2,b2,L,R; cin >> a1 >> b1 >> a2 >> b2 >> L >> R; ll A=a1,B=-1*a2,C=b2-b1; extended_gcd(A,B); if (GCD < 0){ GCD = -1*GCD; solx *= -1; soly *= -1; } if (C%GCD){ cout << 0 << endl; return; } ll l = ceil_div(L-b1,a1), r = floor_div(R-b1,a1); if (r < l){ cout << 0 << endl; return; } l = max(0ll,l); ll pl = ceil_div(C*solx - r*GCD,a2); ll ph = floor_div(C*solx - l*GCD,a2); l = ceil_div(L-b2,a2), r = floor_div(R-b2,a2); l = max(0ll,l); if (r < l){ cout << 0 << endl; return; } pl = max(pl, ceil_div(C*soly - r*GCD,a1)); ph = min(ph,floor_div(C*soly - l*GCD,a1)); if (ph < pl){ cout << 0 << endl; return; } cout << ph-pl+1; }