congruence  一次合同式 a x≡b (mod m) を満たす x を求める

int congruence(int a, int b, int m);

a  合同式にあるa
b  合同式にあるb
m  合同式にあるm

合同式の解xの値（0≦x＜m）。解が存在しないときは-1。

int congruence(int a, int b, int m)
{
    int c, d, e, f;
    int q, r;
    int tmp;
    
    c = a;
    e = b;
    d = m;
    f = 0;
    while ((r = c % d) != 0) {
        q = c / d;
        c = d;
        d = r;
        tmp = f;
        f = e - q * f;
        e = tmp;
    }
    if (b % d != 0) return -1;
    q = (f/d) % (m/d);
    if (q < 0) q += m/d;
    return q;
}