Exploring Linear Diophantine Equation

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