#include <stdio.h>
 
int getInverse(int a, int b)
{
    int x1 = 1, y1 = 0, z1 = a, x2 = 0, y2 = 1, z2 = b, q, t;
    while (z2 > 1) {
        q = z1 / z2;
        x1 -= q * x2,  y1 -= q * y2,  z1 -= q * z2;
        #define SWAP(a, b)  (t = a, a = b, b = t)
        SWAP(x1, x2),  SWAP(y1, y2),  SWAP(z1, z2);
    }
    return x2 < 0 ? x2 + b : x2;
}
 
int main(void)
{
    int r, q;
    while (printf(">> "), scanf("%d%d", &r, &q) == 2)
        printf(" inverse(%d) = %d (mod %d)\n",
                r, getInverse(r, q), q);
    return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiAKaW50IGdldEludmVyc2UoaW50IGEsIGludCBiKQp7CiAgICBpbnQgeDEgPSAxLCB5MSA9IDAsIHoxID0gYSwgeDIgPSAwLCB5MiA9IDEsIHoyID0gYiwgcSwgdDsKICAgIHdoaWxlICh6MiA+IDEpIHsKICAgICAgICBxID0gejEgLyB6MjsKICAgICAgICB4MSAtPSBxICogeDIsICB5MSAtPSBxICogeTIsICB6MSAtPSBxICogejI7CiAgICAgICAgI2RlZmluZSBTV0FQKGEsIGIpICAodCA9IGEsIGEgPSBiLCBiID0gdCkKICAgICAgICBTV0FQKHgxLCB4MiksICBTV0FQKHkxLCB5MiksICBTV0FQKHoxLCB6Mik7CiAgICB9CiAgICByZXR1cm4geDIgPCAwID8geDIgKyBiIDogeDI7Cn0KIAppbnQgbWFpbih2b2lkKQp7CiAgICBpbnQgciwgcTsKICAgIHdoaWxlIChwcmludGYoIj4+ICIpLCBzY2FuZigiJWQlZCIsICZyLCAmcSkgPT0gMikKICAgICAgICBwcmludGYoIiBpbnZlcnNlKCVkKSA9ICVkIChtb2QgJWQpXG4iLAogICAgICAgICAgICAgICAgciwgZ2V0SW52ZXJzZShyLCBxKSwgcSk7CiAgICByZXR1cm4gMDsKfQo=

NSAxMQ==

5 11