RT,大家的exgcd好像都是这么写的:
void exGcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1, y = 0; return; }
exGcd(b, a % b, y, x);
y -= x * (a / b);
return;
}
我的是这么写的:
void exGcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) { x = 1, y = 0; return; }
exGcd(b, a % b, y, x);
y -= x * (a / b);
y += a * (x / b);
x %= b;
return;
}
那么比较广泛的写法为什么不会爆ll?