Solve a Large-Integer Equation
Autumn Tournament (2018)
Submission name: equation.cpp
Problem summary
Find the positive integer x satisfying a·x = b − c. The exact integer solution is guaranteed, but b and c can have more decimal digits than built-in integer types support.
Input
The positive integers a, b, and c, separated by whitespace.
Output
The positive integer x.
Constraints
0 < c < b ≤ 10^100; 0 < a ≤ 10^17; a divides b − c.
Worked example
Official statement sample.
Input
4 20 8
Output
3
Solution analysis
- Compute the decimal difference b − c as a string, from right to left. At each position subtract the matching digit and any borrow; if the result is negative, add ten and borrow from the next column. The promise b > c means a negative big integer is unnecessary.
- Divide the resulting decimal string by a using long division. Before reading each digit, remainder is less than a. After bringing down the next digit, value = 10·remainder + digit is less than 10a, which fits unsigned long long because a ≤ 10^17. Its quotient digit is value/a and the next remainder is value%a.
- For a = 4, b = 20, c = 8, string subtraction gives 12. Long division first takes 1/4 = 0, then 12/4 = 3. Removing leading quotient zeroes prints 3. The same operations work when the difference has one hundred digits.
Why it works
Decimal column subtraction maintains the correct borrow and produces b−c. In long division, the already processed prefix equals a times the quotient prefix plus the maintained remainder. Appending a digit and dividing 10·remainder+digit preserves this invariant. Exact divisibility guarantees a zero final remainder, so the printed quotient is x.
Watch out. Do not parse b or c as long long. Use a 64-bit type for the divisor and remainder, and ensure remainder·10 fits it. Strip leading zeroes without losing the value zero, even though this task guarantees a positive answer.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
string subtractNumbers(string larger,const string&smaller){
int borrow=0;
int j=static_cast<int>(smaller.size())-1;
for(int i=static_cast<int>(larger.size())-1;i>=0;i--){
int digit=larger[i]-'0'-borrow;
if(j>=0){
digit-=smaller[j]-'0';
j--;
}
borrow=digit<0;
if(borrow){
digit+=10;
}
larger[i]=static_cast<char>('0'+digit);
}
size_t first=larger.find_first_not_of('0');
return first==string::npos?"0":larger.substr(first);
}
int main(){
unsigned long long divisor;
string b,c;
cin>>divisor>>b>>c;
string difference=subtractNumbers(b,c);
string quotient;
unsigned long long remainder=0;
for(char digit:difference){
// remainder < divisor, so this intermediate is below 10^18.
unsigned long long value=remainder*10+digit-'0';
quotient+=static_cast<char>('0'+value/divisor);
remainder=value%divisor;
}
size_t first=quotient.find_first_not_of('0');
cout<<(first==string::npos?"0":quotient.substr(first))<<'\n';
}