1380. How Many Ways To Pay Exactly

For each query count the pairs of non-negative integers (x, y) with:

a * x + b * y = c

a = 2, b = 3, c = 10 -> 2 (x,y) = (2,2) and (5,0) a = 2, b = 4, c = 7 -> 0 every combination is even a = 5, b = 3, c = 0 -> 1 only (0,0)

This is the coin question with exactly two denominations and an exact total, and it is the counting half of problem 1338, which finds one solution rather than counting them.

## What most people try first

Loop x from 0 while a*x ≤ c, counting the times (c - a*x) is divisible by b. It is correct and it runs c/a + 1 times, which is 10^18 when a is 1. With 1000 queries that cannot finish.

## The solutions form an arithmetic progression

Let g = gcd(a, b). As in problem 1374, a solution exists only when g divides c, because a*x + b*y is always a multiple of g. When it does, divide through and solve

a' * x ≡ c' (mod b') where a' = a/g, b' = b/g, c' = c/g

which has a unique x modulo b', namely x0 = c' * inverse(a') mod b'. Every solution has x = x0 + t * b' for a whole number t ≥ 0, and y is then determined. So:

• if a * x0 > c there is no non-negative solution at all, because x0 is
• already the smallest valid x;
• otherwise y ≥ 0 requires a*x ≤ c, so the count is how many steps of size
• a * b' fit into c - a*x0, plus one:

count = (c - a*x0) / (a * b') + 1

## Why the step is a*b' and never b

The step in x is b' = b/g, not b. When a and b share a factor the solutions are closer together than b apart, and using b undercounts. a = 4, b = 6, c = 10^18 is in the tests for exactly that reason: the step in x is 3, not 6.

The y ≥ 0 condition needs no separate test. y = (c - a*x)/b is non-negative exactly when a*x ≤ c, which is the condition already counted.

## Overflow

a * b' reaches 10^6 * 10^6 = 10^12, and c reaches 10^18, so both the dividend and the divisor pass what a 32-bit integer can hold, and a 32-bit build answers 0 where the truth is 10^18 + 1. c' * inverse(a') has both factors below b', so under 10^12, which is comfortable in 64 bits. In JavaScript c alone is past 2^53, so BigInt is required.

## Cost

O(log b) per query.

Constraints - `1 ≤ q ≤ 1000` - `1 ≤ a ≤ 1000000` - `1 ≤ b ≤ 1000000` - `0 ≤ c ≤ 1000000000000000000`