1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 */
#include <iostream>
using namespace std;
#define LL long long
int N;
/**
 * extended Euclid's Algorithm  Ax+By = gcd(A, B)
 * @param  a 
 * @param  b 
 * @param  x 
 * @param  y 
 * @return   gcd(a, b)
 */
LL e_gcd(LL a, LL b, LL &x, LL &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    LL m = e_gcd(b, a%b, x, y);
    LL t = x;
    x = y;
    y = t - (a/b)*y;
    return m;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX