Tổng Cây Con

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có một mảng $a$ gồm $N$ số nguyên không âm và một số nguyên $M$ . FJ sẽ chọn một số nguyên $x$ . Với mỗi phần tử $a_{i}$ , chi phí để biến $a_{i}$ thành bội của $M$ cộng $x$ là khoảng cách tối thiểu $| a_{i} - y |$ trong đó $y \equiv x (\mod M)$ .

Độ buồn chán của FJ là tổng chi phí trên tất cả các phần tử. Hãy tìm giá trị nhỏ nhất của độ buồn chán trên mọi cách chọn $x$ .

Dữ liệu vào

Dòng 1: Số nguyên $T$ - số bộ test ( $1 \leq T \leq 10$ )
Với mỗi bộ test:
- Dòng đầu: Hai số nguyên $N$ và $M$
- Dòng sau: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$

Dữ liệu ra

Với mỗi bộ test, in một số nguyên: giá trị buồn chán nhỏ nhất.

Ràng buộc

$1 \leq N \leq 2 \cdot 10^{5}$ , $1 \leq M \leq 10^{9}$
$0 \leq a_{i} \leq 10^{9}$
Tổng $N$ qua tất cả bộ test $\leq 5 \cdot 10^{5}$

Ví dụ

Input	Output	Giải thích
2 5 9 15 12 18 3 8 3 69 1 988244353 998244853	10 21	Bộ test 1: Chọn $x = 6$ , các phần tử cần di chuyển đến $6, 15, 15, 6, 6$ . Tổng chi phí = $\| 15 - 15 \| + \| 12 - 15 \| + \| 18 - 15 \| + \| 3 - 6 \| + \| 8 - 6 \| = 0 + 3 + 3 + 3 + 2 = 11$ . Nhưng $x = 3$ tốt hơn: tổng = 10.

Bình luận

Không có bình luận tại thời điểm này.