+#include "egcd.h"
+
+/*Computes the coefficients of the smallest positive linear combination of two
+ integers _a and _b.
+ These are a solution (u,v) to the equation _a*u+_b*v==gcd(_a,_b).
+ _a: The first integer of which to compute the extended gcd.
+ _b: The second integer of which to compute the extended gcd.
+ _u: Returns the coefficient of _a in the smallest positive linear
+ combination.
+ _v: Returns the coefficient _of b in the smallest positive linear
+ combination.
+ Return: The non-negative gcd of _a and _b.
+ If _a and _b are both 0, then 0 is returned, though in reality the
+ gcd is undefined, as any integer, no matter how large, will divide 0
+ evenly.
+ _a*u+_b*v will not be positive in this case.
+ Note that the solution (u,v) of _a*u+_b*v==gcd(_a,_b) returned is not
+ unique.
+ (u+(_b/gcd(_a,_b))*k,v-(_a/gcd(_a,_b))*k) is also a solution for all
+ k.
+ The coefficients (u,v) might not be positive.*/
+int egcd(int _a,int _b,int *_u,int *_v){
+ int a;
+ int b;
+ int s;
+ int t;
+ int u;
+ int v;
+ /*Make both arguments non-negative.
+ This forces the return value to be non-negative.*/
+ a=_a<0?-_a:_a;
+ b=_b<0?-_b:_b;
+ /*Simply use the extended Euclidean algorithm.*/
+ s=v=0;
+ t=u=1;
+ while(b){
+ int q;
+ int r;
+ int w;
+ q=a/b;
+ r=a%b;
+ a=b;
+ b=r;
+ w=s;
+ s=u-q*s;
+ u=w;
+ w=t;
+ t=v-q*t;
+ v=w;
+ }
+ /*u and v were computed for non-negative a and b.
+ If the arguments passed in were negative, flip the sign.*/
+ *_u=_a<0?-u:u;
+ *_v=_b<0?-v:v;
+ return a;
+}