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 <stdio.h>
#include <stdint.h>
#include <stdlib.h>
struct equation { int64_t mod, rem; };
int64_t extend_gcd(int64_t a, int64_t* x , int64_t b, int64_t* y) {
    *x = 1;
    *y = 0;
    if (b==0) return a;
    int64_t r;
    int64_t q;
    int64_t x0=1, y0=0, x1=0, y1=1;
    *x = 0; *y = 1;
    while ( (r = a % b) ) {
    q = a / b;
    *x = x0 - q * x1;
    *y = y0 - q * y1;
    x0 = x1; x1 = *x; 
    y0 = y1; y1 = *y;
    a = b;  b = r;
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX