Official Analysis

Explanation

Two elements can only collide if they share the same remainder modulo $|K|$, so we handle each remainder class independently.

Within each class, sort the elements in the direction of $K$ (ascending if $K > 0$, descending if $K < 0$). Then greedily ensure each element is strictly past the previous one: if it isn't, advance it by the minimum number of operations needed.

Implementation

Time Complexity: O(N log N)

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;
	while (t--) {
		long long n, k;
		cin >> n >> k;

		map<long long, vector<long long>> groups;
		long long absk = abs(k);
		for (int i = 0; i < n; i++) {
			long long a;
			cin >> a;
			groups[((a % absk) + absk) % absk].push_back(a);
		}

		long long ans = 0;
		for (auto& [r, v] : groups) {
			if (k > 0) {
				sort(v.begin(), v.end());
			} else {
				sort(v.begin(), v.end(), greater<long long>());
			}
			long long prev = v[0];
			for (int i = 1; i < (int)v.size(); i++) {
				if (k > 0) {
					long long next = max(v[i], prev + absk);
					ans += (next - v[i]) / absk;
					prev = next;
				} else {
					long long next = min(v[i], prev - absk);
					ans += (v[i] - next) / absk;
					prev = next;
				}
			}
		}

		cout << ans << "\n";
	}
	return 0;
}