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