Pairs that add to a multiple

Return how many pairs of positions i < j in the list a have a sum a[i] + a[j] that is a multiple of k.

pairs_to_multiple([1, 2, 3, 4, 5], 3)   # 4
pairs_to_multiple([-1, 1, -5, 7], 6)    # 3
pairs_to_multiple([5] * 10, 10)         # 45

Limits

• a has up to 200,000 whole numbers, which may be negative and may be very large. k is from 1 to about a million.
• Checking every pair is far too slow for 200,000 numbers (about 20 billion pairs). The big tests have 3 seconds each.