Diophantine Equation Algorithm
The Diophantine Equation Algorithm, also known as the Euclidean Algorithm, is a mathematical method used to solve linear Diophantine equations, which are equations in the form ax + by = c, where a, b, and c are integers and x and y are unknown variables. The algorithm finds the greatest common divisor (GCD) of two numbers (a and b), which is the largest positive integer that divides both numbers without leaving a remainder. This GCD is important in determining whether the given linear Diophantine equation has integer solutions, as well as finding those solutions.
The algorithm works based on the property that the GCD of two numbers (a and b) is equal to the GCD of the smaller number (b) and the remainder when the larger number (a) is divided by the smaller number (b). The algorithm starts by dividing the larger number by the smaller number and finding the remainder. Then, the smaller number becomes the new larger number and the remainder becomes the new smaller number. This process is repeated until the remainder becomes zero, and the last non-zero remainder is the GCD of the original numbers. If the GCD divides the constant term (c) in the equation, then the linear Diophantine equation has integer solutions. To find these solutions, the Extended Euclidean Algorithm can be used, which not only finds the GCD of two numbers but also expresses it as a linear combination of those two numbers (i.e., GCD(a, b) = ax + by). This provides a method to find the integer solutions of the given linear Diophantine equation.
/************************************************************************************
Solving Diophantine equations in form of a * x + b * y = c
Uses extended Euclid algorithm
(which finds such x, y that a * x + b * y = gcd(a, b))
Based on problem 4188 from informatics.mccme.ru
http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=4188
************************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
long long gcd(long long a, long long b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// Finds such x and y, that a * x + b * y = gcd(a, b)
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
long long x1, y1;
long long g = extended_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
// Solves equation a * x + b * y = c, writes answer to x and y
void solveDiophantine(long long a, long long b, long long c, long long &x, long long &y) {
long long g = extended_gcd(a, b, x, y);
if (c % g != 0) {
puts("Impossible");
exit(0);
}
c /= g;
x = x * c; y = y * c;
}
long long a, b, c;
long long x, y;
long long g;
int main() {
//assert(freopen("input.txt","r",stdin));
//assert(freopen("output.txt","w",stdout));
cin >> a >> b >> c;
// Find any solution
solveDiophantine(a, b, c, x, y);
// In this problem we search for solution with minimum x >= 0
// a * x + b * y = gcd(a, b)
// now for any integer k: a * (x + k * b / g) + b * (y - k * a / g) = gcd(a, b)
g = gcd(a, b);
long long add = b / g;
long long num = 0;
if (add < 0)
num = (long long) floor(1.0 * -x / add);
else
num = (long long) ceil(1.0 * -x / add);
x = x + b / g * num;
y = y - a / g * num;
cout << x << " " << y;
return 0;
}
