拡張版ユークリッドの互除法 84x + 11y = 1 (y > 0)

gojoho.c

#include <stdio.h>

int main()
{
    int L = 84, e = 11;
    int x, x2, y, y2, z, z2, q;
    int tmp;

    x = 1;
    y = 0;
    z = L;
    x2 = 0;
    y2 = 1;
    z2 = e;

    while(z2 != 1){
        if (z2 == 0)
            break;

        q = (z - (z % z2)) / z2;
        x = x - (q * x2);
        y = y - (q * y2);
        z = z - (q * z2);

        tmp = x;
        x = x2;
        x2 = tmp;
    		
        tmp = y;
        y = y2;
        y2 = tmp;

        tmp = z;
        z = z2;
        z2 = tmp;
    }
  
    if(y2 < 0)
        printf("%d\n", y2 + L);
    else
        printf("%d\n",y2);

    return 0;
}