#include "mod.h"

#include <math.h>
#include <assert.h>
#include <stdio.h>

//num p = 2147483647; // 2^31 - 1
//num p = 20021; // 2^31 - 1

extern inline num mod(num a, num b);
extern inline num mulmod(num a, num b);
extern inline num divmod(num a, num b);
extern inline num submod(num a, num b);
extern inline num addmod(num a, num b);

num Extended_Euclid(num A, num B, num *X, num *Y){
    num x, y, u, v, m, n, a, b, q, r;
 
    /* B = A(0) + B(1) */
    x = 0; y = 1;
 
    /* A = A(1) + B(0) */
    u = 1; v = 0;
 
    for (a = A, b = B; 0 != a; b = a, a = r, x = u, y = v, u = m, v = n) {
        /* b = aq + r and 0 <= r < a */
        q = b / a;
        r = b % a;
 
        /* r = Ax + By - aq = Ax + By - (Au + Bv)q = A(x - uq) + B(y - vq) */
        m = x - (u * q);
        n = y - (v * q); 
    }   
 
    /* Ax + By = gcd(A, B) */
    *X = x; *Y = y;
 
    return b;
}
