cho (\mathbf{k}) (2modk.*)

Cho số nguyên dương \(n\) và dãy số \(a_{1},a_{2},\ldots,a_{n}\) trong đó \(a_{i} = i\). Hãy cho biết có bao nhiêu cặp số \((a_{i},a_{j})\) mà \(a_{i} + a_{j}\) chia hết cho \(k\) và \(i < j\).

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(t\ (t \leq 100)\) cho biết số lượng testcase

+ \(t\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương lần lượt là \(n\) và \(k\ (1 \leq k \leq n \leq 10000);\)

Kết quả:

+ Mỗi testcase in kết quả trên một dòng

Ví dụ:

Input	Output
2 10 4 7 3	10 7

Solution

Ta có công thức: \((a + b)\% c = (a\% c + b\% c)\% c\)

suy ra, nếu \((a + b)\% c = 0\) thì \((a\% c + b\% c)\% c = 0\)

Do vậy, với dãy số \(1,2,3,\ldots,n\) ta thực hiện chia mỗi số cho \(k\). Dãy số trở thành

\[\mathbf{1,2,\ldots,k - 2,k - 1,0,1,2,\ldots,k - 2,k - 1,0},\ldots\ldots 1,2,\ldots n\% k\]

Ta sẽ có đúng \(n/k\) đoạn \(\mathbf{1,2,\ldots,k - 2,k - 1,0}\) và đoạn còn lại \(1,2,\ldots n\% k\) xuất hiện chỉ 1 lần

Có thể thấy với ví dụ \(n = 10;k = 4\); dãy số sau khi chia lấy dư toàn bộ cho \(k\) là:

\[\mathbf{1,2,3,0,1,2,3,0,}1,2\]

Bài toán trở thành: tìm cặp số \(a_{i},a_{j}\) để \(a_{i} + a_{j} = k\) với \(i < j\)

Với nhận xét như trên ta dễ dàng đếm được số lần xuất hiện của mỗi số:

\(d\lbrack i\rbrack = \frac{n}{k}\) (với \(i = 0\ldots k - 1\))

\(d\lbrack i\rbrack + +\) (với \(i = 1\ldots n\% k\))

Sau khi có được \(d\lbrack i\rbrack\) là số lần xuất hiện của giá trị \(i\) trong dãy số (sau khi chia lấy dư cho \(k\)) ta thấy: một số \(i\) sẽ kết với một số \(k - i\) để tạo thành một cặp số có tổng đúng bằng \(k\)

Như vậy kết quả là \(ans = d\lbrack i\rbrack \times d\lbrack k - i\rbrack\) (với \(i = 1\ldots k/2 + k\% 2 - 1\))

Tất nhiên sẽ không quên xét đến \(d\lbrack 0\rbrack\): \(ans + = d\lbrack 0\rbrack \times (d\lbrack 0\rbrack - 1)/2\);

Lưu ý với \(k\) chẵn thì cần tính thêm: \(ans + = d\lbrack k/2\rbrack \times (d\lbrack k/2\rbrack - 1)/2\);