Algorithm optimization C++

Question

I'm trying to complete a homework assignment that involves finding out for any three non-negative numbers a,b and c, if c can be reached by adding a and b to one another. Example:

if a = 3, b = 5, c = 19 we would do the following 1st step: (3,5) 2nd step: (3,8) 3rd step: (11,8) 4th step: (19,8) thus c has been reached.

This involves finding all positive solutions to the equation c = xa + yb and checking whether the GCD(x,y) = 1. If it is, the answer is yes, otherwise, the answer is no.

 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
       }

This is the part of the code that I need help optimizing. In order to find the solutions, I iteratively reduce c by a which I set to be max(a,b) and once I take out all the 'a's from c, I get a number that is divisible by b and have therefore found a solution. I divide that number by b, and the result is the y part of the solution, after which I divide what I've taken out of c by a, and get the x part of the solution.

Is there any way I can find positive solutions x and y faster? I've heard of the Extended Euclidean Algorithm, but I have no idea how to implement it.