3 /*Computes the coefficients of the smallest positive linear combination of two
5 These are a solution (u,v) to the equation _a*u+_b*v==gcd(_a,_b).
6 _a: The first integer of which to compute the extended gcd.
7 _b: The second integer of which to compute the extended gcd.
8 _u: Returns the coefficient of _a in the smallest positive linear
10 _v: Returns the coefficient _of b in the smallest positive linear
12 Return: The non-negative gcd of _a and _b.
13 If _a and _b are both 0, then 0 is returned, though in reality the
14 gcd is undefined, as any integer, no matter how large, will divide 0
16 _a*u+_b*v will not be positive in this case.
17 Note that the solution (u,v) of _a*u+_b*v==gcd(_a,_b) returned is not
19 (u+(_b/gcd(_a,_b))*k,v-(_a/gcd(_a,_b))*k) is also a solution for all
21 The coefficients (u,v) might not be positive.*/
22 int egcd(int _a,int _b,int *_u,int *_v){
29 /*Make both arguments non-negative.
30 This forces the return value to be non-negative.*/
33 /*Simply use the extended Euclidean algorithm.*/
51 /*u and v were computed for non-negative a and b.
52 If the arguments passed in were negative, flip the sign.*/