Paying with two coins

You have as many coins of value a and of value b as you like. Return the number of ways to pay exactly amount: the number of pairs (x, y) of whole numbers, both 0 or more, with a * x + b * y == amount.

pay_ways(3, 5, 30)    # 3: (10, 0), (5, 3), (0, 6)
pay_ways(4, 6, 9)     # 0: 4x + 6y is always even
pay_ways(3, 5, 7)     # 0
pay_ways(3, 5, 0)     # 1: no coins

pow() is switched off for this problem, so its inverse shortcut (lesson 5) is not available: use the extended Euclidean algorithm from lesson 1.

Limits

• a and b are from 1 to about 10¹⁸ (a 1 followed by 18 zeros); amount is from 0 to 10³⁶ (a 1 followed by 36 zeros).
• Trying every number of a-coins is far too slow for big amounts. The tests with big numbers have 2 seconds each.