Diophantine equation

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