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;
}
