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;
}