Из http://en.wikipedia.org/wiki/Diophantine_equation
"
Linear Diophantine equations take the form ax + by = c. If c is the greatest common divisor of a and b then this is Bézout's identity, and the equation has an infinite number of solutions. These can be found by applying the extended Euclidean algorithm. It follows that there are also infinite solutions if c is a multiple of the greatest common divisor of a and b. If c is not a multiple of the greatest common divisor of a and b, then the Diophantine equation ax + by = c has no solutions.
"
Т.е. значала проверяем, есть ли решения вообще.
(если C mod gcd(A, B) <> 0, то их нет).

Если есть, то решение существует.
Далее, как найти это решение?

Далее примем d = gcd(A, B)

Существует тождество Безу
http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity

Оно выглядит так Ax+By=GCD(A, B).
Решается расширенным Эвклидом.

Наше уравнение не является тождеством Безу, но
можно решить тождество A*x' + B*y'=GCD(A, B) с нашими A, B Эвклидом.

Оно немного отличается от нашего уравнения Ax+By=-C.
Чем? Тем, что мы решаем его не для правой части = -C, а для d, т.е. для правой части, которая в сколько то раз (в -C/d) меньше, чем -С.


Следовательно,

x = x'*(-C/d), y = y'*(-C/d)
(полученные x', y' просто умножаются на то, во сколько раз -C больше d).
Минус появляется при переносе знака C.

В коде:

    d = extended_gcd(a, b);
    if (c % d != 0)
        cout <<-1;
    else
        cout <<lastx * (-c / d)<<" " <<lasty * (-c / d);

lastx, lasty- рез-ты работы расширенного алгоритма Эвклида.