Bạn có một mảng số nguyên \(a_1\dots a_N\), ban đầu các phần tử nằm trong đoạn \([1,N]\) (\(1\le N\le 2\cdot 10^5\)), cùng với một số nguyên khác không \(K\) (\(-N\le K\le N, K\neq 0\)).

Bạn có thể thực hiện thao tác sau bao nhiêu lần tùy thích (có thể không lần nào): chọn một chỉ số \(i\) và gán \(a_i=a_i+K\).

Hãy tìm số thao tác ít nhất để tất cả các phần tử của mảng đôi một khác nhau.

Dữ liệu vào

Dữ liệu vào gồm \(T\) (\(1\le T\le 10\)) bộ test độc lập. Mỗi bộ test được mô tả như sau:

Dòng đầu tiên chứa \(N\) và \(K\).

Dòng thứ hai chứa \(a_1\dots a_N\).

Đảm bảo tổng \(N\) trên tất cả các bộ test không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ test, in một dòng chứa số thao tác ít nhất.

Lưu ý: Do các số nguyên trong bài có thể rất lớn, bạn có thể cần sử dụng kiểu số nguyên 64 bit (ví dụ, long long trong C/C++).

Ví dụ

4
4 1
4 1 4 1
4 -3
4 1 4 1
4 4
4 1 4 1
3 -1
1 1 2

2
4
2
1

4 1 4 1
5 1 4 1 (a_1 += 1)
5 1 4 2 (a_4 += 1)

Phân nhóm

• Dữ liệu 2-4: \(N\le 50\).
• Dữ liệu 5-7: \(N\le 2000\).
• Dữ liệu 8-10: \(K=1\).
• Dữ liệu 11-13: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Bronze — Make All Distinct. Tác giả: Akshaj Arora, Benjamin Qi.
https://usaco.org/index.php?page=viewproblem2&cpid=1587