GVZ's Blog
void exgcd(int a, int b, int& d, int& x, int& y) { if(b) exgcd(b, a % b, d, y, x), y -= a / b * x; else d = a, x = 1, y = 0; }