Nearest Equation Solution
National Olympiad — Municipal round (2021 season)
Submission name: equation.cpp
Problem summary
For each test, solve a*x + b*y = c in integers. Choose x nearest to p; if tied, choose the larger x.
Input
N, followed by N lines a b c p.
Output
For each test, print x y, or 0 0 if no integer solution exists.
Constraints
0 < N < 100; 0 < a,b,c < 10^9; −10^9 < p < 10^9.
Worked example
An independently prepared example for this explanation.
Input
3 7 6 5 8 2 4 1 1 2 3 1 -4
Output
11 -12 0 0 -4 3
Solution analysis
- Extended Euclid gives g = gcd(a,b) and coefficients u,v with a*u+b*v=g. A solution exists exactly when g divides c. Then x is congruent to u*(c/g) modulo step = b/g.
- Normalize one such x to a residue r in [0,step). All feasible x values form the arithmetic progression r+k*step. Find the two progression values bracketing p using mathematical floor division; compare their distances and take the upper one on a tie.
- For 7*x+6*y=5, x is congruent to 5 modulo 6. Around p=8 the candidates are 5 and 11, both distance three, so choose x=11 and y=−12. For 2*x+4*y=1, gcd 2 does not divide 1, so output 0 0.
Why it works
Bézout’s identity proves divisibility is sufficient, and every integer solution differs in x by a multiple of b/g. A point in an arithmetic progression nearest p must be one of its two neighbors around p; comparing them and favoring the upper enforces both optimization rules. Computing y=(c−a*x)/b then gives an integer satisfying the equation.
Watch out. C++ integer division truncates toward zero; adjust negative quotients to implement floor. Normalize negative modular residues. Use 64-bit arithmetic for coefficient scaling and a*x.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
long long extendedGcd(long long a,long long b,long long&x,long long&y){
if(b==0){
x=1;
y=0;
return a;
}
long long nextX,nextY;
long long divisor=extendedGcd(b,a%b,nextX,nextY);
x=nextY;
y=nextX-(a/b)*nextY;
return divisor;
}
long long floorDivide(long long value,long long divisor){
long long quotient=value/divisor;
if(value%divisor<0){
--quotient;
}
return quotient;
}
int main(){
int tests;
cin>>tests;
while(tests--){
long long a,b,c,target,x,y;
cin>>a>>b>>c>>target;
long long divisor=extendedGcd(a,b,x,y);
if(c%divisor!=0){
cout<<"0 0\n";
continue;
}
long long step=b/divisor;
long long residue=(x*(c/divisor))%step;
if(residue<0){
residue+=step;
}
long long lower=residue+floorDivide(target-residue,step)*step;
long long upper=lower+step;
// The upper candidate wins equal-distance ties.
x=target-lower<upper-target?lower:upper;
y=(c-a*x)/b;
cout<<x<<' '<<y<<'\n';
}
}