Алгоритм оптимизации переполнения стека

Я пытаюсь выполнить домашнее задание, которое включает в себя выяснение любых трех неотрицательных чисел a, b и c, можно ли достичь c, добавив a и b друг к другу. Пример:

если a = 3, b = 5, c = 19, мы бы сделали следующее
1-й шаг: (3,5)
2-й шаг: (3,8)
3-й шаг: (11,8)
4-й шаг: (19,8) Таким образом, с был достигнут.

Это включает в себя поиск всех положительных решений уравнения с = ха + уb и проверка, является ли GCD (x, y) = 1. Если это так, ответ — да, в противном случае ответ — нет.

 long long int cc = c; //saving the starting value of c
c=c-a; //a has to be in c at least once
while(c>0){  // we reduce c by a in each step until b divides c, which would mean we found
if(c%b==0){ //solutions to c=xa+yb or until c becomes <=0
y = (c/b);   //evaluating y
x = ((cc - c)/a); //evaluating x
if(gcd(x,y)==1) //if it's correct, then it's possible, otherwise try other solutions
return true;
}
c=c-a; //reduce c by a
}

Это та часть кода, которая мне нужна для оптимизации. Чтобы найти решения, я итеративно уменьшаю c на a, для которого я установил max (a, b), и как только я вынимаю все ‘a из c, я получаю число, которое делится на b, и поэтому нашло решение. Я делю это число на b, и в результате получается часть y решения, после которой я делю то, что я вынул из c на a, и получаю часть решения x.

Есть ли способ найти положительные решения х и у быстрее? Я слышал о расширенном евклидовом алгоритме, но понятия не имею, как его реализовать.