Problem Statement

Discounted Product Pairs A store is running a promotion: a discount applies to every purchase of a pair of products whose combined cost is divisible by x . You are given the costs of n products in the store. Count the number of index pairs (i, j) with i < j such that cost[i] + cost[j] is divisible by x . Input Format The first line contains the integer x . The second line contains the integer n , the number of products. Each of the next n lines contains one integer, cost[i] . Output Format Print a single integer: the number of pairs (i, j) with i < j whose costs sum to a multiple of x . Constraints 1 <= x <= 2 * 10^9 1 <= n <= 15000 1 <= cost[i] <= 10^9 Example 60 5 31 25 85 29 35 Output: 3 There are n = 5 products, x = 60 and cost = [31, 25, 85, 29, 35] . The qualifying pairs are (31, 29) , (25, 35) and (85, 35) ; each sums to a multiple of 60 . Sample Case 0 Input: 10 4 3 7 27 23 Output: 4 The pairs that get the discount are (3, 7) , (3, 27) , (23, 7) and (23,