I did this in O(n)

for(int i = 0; i < n; i++){
    cin >> a[i];
    m[a[i]%k]++;
}

(A+B) mod C = ((A mod C) + (B mod C)) mod C

for (int i=1; i<=k/2 && i!=k; i++)
    sum += m[i]*m[k-i];

public static void Main(string[] args)
{
	// First input line contains n and k. Ignore n because it will be
	// implied by the second input line.
	int k = int.Parse(Console.ReadLine().Split(' ')[1]);

	// When reading the line, we only care about each value mod k.
	// Read the line in, and convert it to a dictionary/map with
	// value-mod-k as key, and the number of times that value-mod-k
	// occurs as the value.
	var modCounts = Console.ReadLine()
		.Split(' ')
		.Select(x => int.Parse(x) % k).GroupBy(x => x)
		.ToDictionary(x => x.Key, x => x.Count());

	// Initialize the result
	int result = 0;

	// We only need to check the first k/2 keys (plus the middle key
	// if k is odd), because the other keys are "complementary" (may
	// not be the correct term, see comment below) to the ones we check.
	for (int modValue = 0; 2 * modValue <= k; modValue++)
	{
		int modCount;

		// If modCounts does not contain the key modValue, then modCount will
		// be 0.
		modCounts.TryGetValue(modValue, out modCount);

		// "Complement" may not be the correct term for this. As I'm using it,
		// complement(n) with respect to k is defined as the value c
		// such that (n + c) % k == 0 and c % k == 0.
		var complementValue = (k - modValue) % k;
		if (modValue == complementValue)
		{
			// If modValue == complementValue (which happens if modValue == 0,
			// or if modValue == (k + 1) / 2 and k is odd), then each occurrence
			// of modValue pairs with other occurrences of the same modValue.
			// The number of pairs within modCount identical values is
			// Sum (from i=1 to modCount-1) of i.
			// Sum (from i=1 to n) of n is ((n * (n + 1)) / 2), which is equivalent to
			// (n^2 + n) / 2. With n = modCount - 1:
			// ((modCount - 1)^2 + (modCount - 1) / 2
			// ((modCount^2 - 2 * modCount + 1) + (modCount - 1)) / 2
			// (modCount^2 - modCount) / 2
			result += modCount * (modCount - 1) / 2;
		}
		else
		{
			// In the normal case, modValue != complementValue, we just have
			// modCount * complementCount pairs.
			int complementCount;
			modCounts.TryGetValue(complementValue, out complementCount);
			result += modCount * complementCount;
		}
	}

	Console.WriteLine(result);
}

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main() 
{
	int n, k;

	cin >> n >> k;

	vector<int> complenemts(k);

	int count = 0;

	int temp;
	for (int i = 0; i < n; ++i)
	{
		cin >> temp;

		int remainder = (temp % k);

		int complenemt = (k - remainder) % k;

		count += complenemts[remainder];

		complenemts[complenemt] += 1;
	}

	cout << count;

	return 0;
}

public static void CountMatch(int[] num, int k){      
        int count = 0;
        //store mod and such counts
        Dictionary<int,int> dict  = new Dictionary<int, int>();
          
        foreach(int n in num){
          int mod = n%k;
          int need = (k-mod) % k;
            
          //check if the dictionary has the balance
          if(dict.ContainsKey(need)){
              count += dict[need];
          }
          
          //increment/add mod to dictionary
          if(dict.ContainsKey(mod)){
              dict[mod]+=1;
          }
          else{
           dict.Add(mod, 1);    
          }
        }      
        Console.WriteLine(count);
    }

def divisibleSumPairs(n, k, ar):
    return sum(1 for i in range(n) for j in range(n) if i < j and (ar[i]+ar[j])%k == 0)

count += rem[k/2] * (k%2 == 0) ? (rem[k/2] - 1) / 2 : rem[k/2] - i;

if( k%2 == 0) count += (rem[k/2] * (rem[k/2]-1)) / 2;
else count += rem[k/2] * (rem[k-i]);

static int divisibleSumPairs(int n, int k, int[] arr) {
    int pairCount = 0;

    // create an array with length equal to all reminders
    // available to k (0 to k-1 reminders)
    int[] remainderCountList = new int[k];

    for (int i = 0; i < arr.length; i++) {
        int remainder = arr[i] % k;
        remainderCountList[remainder]++;
    }

    // Now that the remainders have been counted, all that
    // produced a remainder of 0, can only be paired 
    // between themselves, so, if say, there were 4 
    // numbers, we can make up to six pairs 
    // i.e. (0,1) (0,2) (0,3), (1,2), (1,3), (2,3)
    int exactCount = remainderCountList[0];
    // all elements against a subset of one less of itself
    // and only half the pairs can be used
    pairCount += (exactCount * (exactCount-1)) / 2;

    // Now, for all other remainders, pairs are of those
    // that are complementing remainders
    // i.e. if K = 5, remainders would be 0, 1, 2, 3, 4
    // we know that 0 has already been accounted for
    // so, next pairs are all of those in 1 with 4 and
    // all those in 2 with 3
    // So we only need to iterate through half of the
    // remaining remainders, and make sure that we don't
    // use a reaminder against itself for this calculation
    for (int i = 1; i <= k/2 && i != k-i; i++) {
        pairCount += remainderCountList[i] * remainderCountList[k-i];
    }

    // Finally, there is one more case to consider, if K
    // yields an even number of remainders, the loop above
    // would have skipped the exact middle remainder.
    // i.e. for k = 4, remainders = 0, 1, 2, 3
    //   0 has been accounted for
    //   1 and 3 were paired up
    //   2 is missing
    // This last remainder behaves like the 0 remainder, 
    // so, we need to pair the numbers against themselves
    if (k % 2 == 0) {
        int halfCount = remainderCountList[k/2];
        pairCount += (halfCount * (halfCount-1)) / 2;
    }

    return pairCount;
}

def search(numbers,k):
    numberofways=int()
    for i in range(len(numbers)-1):
        for j in range(i+1,len(numbers)):
            if (numbers[i]+numbers[j])%k==0:
                numberofways+=1
    return numberofways
number=list()
n=int(input())
k=int(input())
for i in range(n):
    number.append(int(input()))
print(search(number,k))

def divisibleSumPairs(n, k, ar)
    pairs = 0
    h = Hash.new(0).tap { |h| ar.each { |num| h[num%k] += 1 }}
    h.each do |key, val|
        compatikey = k - key
        compatival = h[compatikey]
        if key == compatikey || key == 0
            pairs += ((1..(val-1)).inject(:+) || 1) if val > 1
        elsif compatival > 0
            pairs += (val * compatival)
        end
        h.delete(key)
        h.delete(compatikey)
    end
    return pairs
end

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int a[] = new int[n];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
        }
        
        int count=0;
        //checking aginst the condition
        for(int i=0;i<(n-1);i++){
            for(int j=0;j<n;j++){
                if(i<j){
                    if((a[i]+a[j])%k==0)
                        count++;
                }
            }
        }
        System.out.println(count); 
    }
}

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int a[] = new int[k];
        int count = 0;
        for(int i=0; i < n; i++){
            int remainder  = in.nextInt() % k;
            int complement = (remainder == 0) ? 0:k-remainder;
            count += a[complement];
            a[remainder]++;
        }
        System.out.println(count);
    }

return IntStream.range(0,n).map(x -> IntStream.range(x+1,n).map(y -> (ar[x]+ar[y])%k==0?1:0).sum()).sum();

int complement = number == 0 ? 0 : k-number;
count += a[complement];

for(int i = 0;i < n;i++)
{
    for(int k = i+1; k < n;k++)
    {
    
    
/*a[k] access unknown memory when "i = n-1". undefined behavior. It just happen to work in this instance.
**/
        if((a[i] + a[k]) % l == 0 && i < k)
            count++;
    }
}

count += counts[(k - bucket) % k];
        counts[bucket]++;

function divisiblesumpairs (n, k, a) {
	let compls = new Map(),
	count = 0;

	for (let i = 0; i < n; i++) {
		let m = a[i] % k,
			c = (k - m) % k,
			p, q;

		if (p = compls.get(m))
			count += p;
		
		if (q = compls.get(c))
			compls.set(c, ++q)
		else
			compls.set(c, 1)
	}
	return count;
}