最小公倍数&扩展欧几里得模板（更新）
欧几里得：
int gcd(int a,int b) {
if(!b) return a;
while((a%=b) && (b%=a));
return a+b;
} 扩展欧几里得：
int exgcd(int a, int b, int &x, int &y) {
int x1 = 1, x2 = 0, x3 = 0, x4 = 1;
while (b != 0) {
int c = a / b;
tie(x1, x2, x3, x4, a, b) =
make_tuple(x3, x4, x1 - x3 * c, x2 - x4 * c, b, a - b * c);
}
x = x1, y = x2;
return a;
} 