def divisible_sum_pairs(n: int, k: int, ar: list[int]):
    #Time complexity: O(n+k)
    #Space complexity (ignoring input): O(k)
    possible_remainders = {}
    total_pairs = 0

    for number in ar:
        remainder = number % k
        if remainder in possible_remainders:
            possible_remainders[remainder] += 1
        else:
            possible_remainders[remainder] = 1

    # For remainder 0 or k/2, the total pairs will be n choose 2
    if 0 in possible_remainders:
        total_pairs += int(possible_remainders[0] * (possible_remainders[0] - 1) / 2)
    k_is_pair = k % 2 == 0
    half_k = int(k / 2)
    if k_is_pair and (half_k in possible_remainders):
        total_pairs += int(
            possible_remainders[half_k] * (possible_remainders[half_k] - 1) / 2
        )

    # For the rest of the remainders, just need to multiply
    for remainder in range(1, int((k + 1) / 2)):
        if (remainder in possible_remainders) and (
            (k - remainder) in possible_remainders
        ):
            total_pairs += int(
                possible_remainders[remainder] * (possible_remainders[k - remainder])
            )

    return total_pairs