欧几里得(gcd) + 拓展欧几里得(ext_gxd)

1. 欧几里得算法

//求最大公约数和最小公倍数

int gcb(int a, int b){return b == 0 ? a : gcb(b, a%b);
}

2.拓展欧几里得

求解线性方程组 ax + by + c = 0

void gcd(int a, int b, int &x, int &y, int &d){if(!b){d = a;x = 1;y = 0;}else{gcd(a, a%b, x, y, d);y -= x*(a/b);}
}

//计算乘法逆元

int extgcd(ll a, ll b, ll &x, ll &y){if(b == 0){x = 1;y = 0;return a;}else{ll ans = extgcd(b, a%b, x, y);ll t = x;x = y;y = t - a/b*y;return ans;}
}
//计算乘法逆元
int cal(ll a, ll b, ll d){ll x, y;ll gcd = extgcd(a, b, x, y);if(d % gcd != 0) return -1;x = x*d/gcd;b = b/gcd;if(b < 0) b = -b;ll ans = x%b;if(ans < 0) ans += b;return ans;
}