Linear Diophantine Equations

A linear Diophantine equation asks for integer solutions to ax+by=c. Real-number division alone does not solve the integrality requirement. Extended Euclid supplies one solution when the GCD divides c; a single integer parameter then describes every solution. We also count those lying in an inclusive rectangle, so careful floor/ceiling division and zero-coefficient cases are part of the algorithm.

Prerequisites: Extended Euclidean Algorithm; signed floor division.

Build the idea

1. 1. Establish existence

   Every integer combination ax+by is divisible by g=gcd(|a|,|b|), so g must divide c. Conversely, if g divides c, multiply Bézout coefficients by c/g and adjust for original coefficient signs to construct x₀,y₀. Thus the condition is sufficient as well as necessary. If a=b=0, the equation is either impossible when c≠0 or true for every integer pair when c=0.

2. 2. Describe the whole family

   Adding b/g to x and subtracting a/g from y leaves ax+by unchanged. Every solution differs from the constructed one by these steps because, after dividing by g, the coefficients are coprime. Therefore one integer t parameterizes all solutions.

   $$x=x_0+\frac{b}{g}t,y=y_0-\frac{a}{g}t$$

3. 3. Convert coordinate bounds into parameter bounds

   For low≤base+step·t≤high and positive step, t ranges from ceil((low−base)/step) to floor((high−base)/step). Reverse the endpoint formulas for negative step. If step is zero, the fixed base must already be inside its coordinate bounds. Intersect the x and y parameter intervals; the number of integers is max(0,to−from+1). C++ truncation is not floor for arbitrary signs, so dedicated helpers adjust nonzero remainders.

4. 4. Work 4x+6y=14

   GCD is 2, which divides 14. Extended Euclid gives one solution (−7,7) and steps (3,−2). With both coordinates in 0..5, x bounds require t=3..4 and y bounds require t=1..3; their intersection is only t=3. The unique bounded pair is (2,1). The printed particular solution may lie outside the rectangle: it describes the full family, while the final line separately counts bounded members.

5. 5. Treat degeneracy and overflow as real cases

   When only one coefficient is zero, the general parameter method still works: one coordinate step is zero and the other varies freely. When both are zero and c=0, count all rectangle grid points directly. Inputs and bounds here have magnitude≤10^6, keeping coefficient scaling, parameter differences and rectangle counts within long long. A general full-range implementation would need stronger overflow handling.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<algorithm>
#include<cstdlib>
using ll=long long;
ll extended(ll a,ll b,ll&x,ll&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1,g=extended(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1; // Substitute the smaller equation back into a,b.
    return g;
}
ll floorDivide(ll a,ll b){
    ll q=a/b,r=a%b;
    if(r!=0&&((r>0)!=(b>0))){
        --q;
    }
    return q;
}
ll ceilDivide(ll a,ll b){
    ll q=a/b,r=a%b;
    if(r!=0&&((r>0)==(b>0))){
        ++q;
    }
    return q;
}
bool restrictRange(ll base,ll step,ll low,ll high,ll&from,ll&to){
    if(step==0){
        return low<=base&&base<=high;
    }
    ll a,b;
    if(step>0){
        a=ceilDivide(low-base,step);
        b=floorDivide(high-base,step);
    }
    else{
        a=ceilDivide(high-base,step);
        b=floorDivide(low-base,step);
    }
    from=std::max(from,a);
    to=std::min(to,b);
    return from<=to;
}
int main(){
    ll a,b,c,lx,rx,ly,ry;
    std::cin>>a>>b>>c>>lx>>rx>>ly>>ry;
    if(a==0&&b==0){
        if(c!=0){
            std::cout<<"NO\n";
        }
        else{
            std::cout<<"ALL\n"<<(rx-lx+1)*(ry-ly+1)<<'\n';
        }
        return 0;
    }
    ll x,y,g=extended(std::abs(a),std::abs(b),x,y);
    if(c%g!=0){
        std::cout<<"NO\n";
        return 0;
    }
    x*=c/g;
    y*=c/g;
    if(a<0){
        x=-x;
    }
    if(b<0){
        y=-y;
    }
    ll dx=b/g,dy=-a/g;
    ll from=-1000000000000000000LL,to=1000000000000000000LL;
    bool possible=restrictRange(x,dx,lx,rx,from,to)&&restrictRange(y,dy,ly,ry,from,to);
    std::cout<<x<<' '<<y<<'\n'<<dx<<' '<<dy<<'\n';
    std::cout<<(possible?to-from+1:0)<<'\n';
}

Complexity analysis

O(log(max(|a|,|b|)+1)) time and recursion space for Extended Euclid, followed by O(1) interval intersection. The both-zero branch is O(1). Count depends on parameter bounds rather than enumerating every candidate point, which can be much larger.

Example input and output

Read a b c lx rx ly ry, all |values|≤10^6 with lx≤rx and ly≤ry. If impossible print NO. For a=b=c=0 print ALL and rectangle count. Otherwise print one algebraic solution x₀ y₀, parameter steps dx dy, then number of bounded solutions.

Input

4 6 14 0 5 0 5

Output

-7 7
3 -2
1

Only t=3 in (−7+3t,7−2t) lies in the box, yielding (2,1).

Practical applications

Use for integer resource equations, lattice-line intersections and modular linear equations. For more variables, the two-variable parameter form is not sufficient by itself. When only an inverse is needed, normalize one Bézout coefficient instead of counting a rectangle.

Check your understanding

When does ax+by=c have integer solutions for nonzero (a,b)?

Put it into practice

Compare counts with enumerating all points in tiny signed rectangles.