1379. Write the gcd As a Combination

For each query, find integers x and y with:

a * x + b * y = gcd(a, b)

Such a pair always exists. That is Bezout's identity, and it is the reason the extended Euclidean algorithm is worth knowing at all.

There are infinitely many pairs, so one is pinned: print the pair with the smallest non-negative `x`, which is the same rule problem 1338 uses. y is then forced, and may be negative.

a = 3, b = 5 -> 2 -1 3*2 + 5*(-1) = 1 a = 6, b = 9 -> 2 -1 6*2 + 9*(-1) = 3 a = 7, b = 1 -> 0 1 7*0 + 1*1 = 1

## What most people try first

Search x upward, testing whether (g - a*x) is divisible by b. It works and it is O(b/g) per query, which is 10^9 at the limits.

## Carry the coefficients through Euclid

Ordinary Euclid replaces (r0, r1) by (r1, r0 mod r1). Carry two extra columns saying how each remainder is built from a and b:

``` r: a b s: 1 0 so r = a*s + b*t holds for both rows t: 0 1

each step: q = r0 / r1 (r0, r1) = (r1, r0 - q*r1) (s0, s1) = (s1, s0 - q*s1) (t0, t1) = (t1, t0 - q*t1) ```

The identity r = a*s + b*t is preserved by every step, because the new row is a linear combination of two rows that already satisfy it. When r1 reaches 0, r0 is the gcd and its s and t are a Bezout pair.

## Pinning the answer

If (x, y) works then so does (x + b/g, y - a/g), and those are all of them. So reducing x modulo b/g into 0 .. b/g - 1 gives the smallest non-negative x, and y = (g - a*x) / b follows. That division is always exact, because a*x ≡ g (mod b) is exactly what reducing x preserved.

Note b/g can be 1, in which case x is always 0.

## Overflow

a and x are both below 10^9, so a * x reaches 10^18. A signed 64-bit integer holds that; a 32-bit one stops at 2147483647 and gets y wrong while still printing the right x, which is a particularly quiet failure. In JavaScript a Number is exact only below 2^53, so BigInt is needed. The intermediate coefficients inside the loop stay bounded by max(a, b), so the loop itself never overflows.

## Cost

O(log min(a, b)) per query.

Constraints - `1 ≤ q ≤ 1000` - `1 ≤ a ≤ 1000000000` - `1 ≤ b ≤ 1000000000` - Among the infinitely many pairs, print the one with the smallest non-negative `x`.