https://www.acwing.com/problem/content/6134/

又是农夫约翰的农场上寒冷而无聊的一天。

为了打发时间，农夫约翰发明了一种关于在整数数组上进行操作的有趣的休闲活动。

农夫约翰有一个包含 $N$ 个非负整数的数组 $a$ 和一个整数 $M$。

然后，农夫约翰会请贝茜给出一个整数 $x$。

在一次操作中，农夫约翰可以选择一个索引 $i$，并对 $a_i$ 加 $1$ 或减 $1$。

农夫约翰的无聊值是他必须执行的最小操作次数，以使得对于所有的 $1 \leq i \leq N$，$a_i - x$ 均可被 $M$ 整除。

对于所有可能的 $x$，输出农夫约翰的最小无聊值。

输入格式 输入的第一行包含 $T$，为需要求解的独立的测试用例数量。

每一个测试用例的第一行包含 $N$ 和 $M$。

第二行包含 $a_1, a_2, \ldots, a_N$。

输出格式 对于每一个测试用例输出一行，包含对于所有可能的 $x$，农夫约翰的最小无聊值。

数据范围

• $1 \leq T \leq 10$
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 10^9$
• $0 \leq a_i \leq 10^9$
• 输入保证所有测试用例的 $N$ 之和不超过 $5 \times 10^5$。

输入样例：

2
5 9
15 12 18 3 8
3 69
1 988244353 998244853

输出样例：

10
21

样例解释 在第一个测试用例中，$x$ 的一个最优选择是 $3$。

农夫约翰可以执行 $10$ 次操作使得 $a=[12,12,21,3,12]$。

如下题解
https://www.acwing.com/solution/content/267673/

一些补充：
- 为什么直接转换为模上m的值，然后再直接找这些值中用最少的改变次数使他们相等，也就是找一个点使每个值到这个点距离相等不行？
因为这些都是取模之后的数，假如我们这些数都模9，最后找的点为1，那原来数值为8的点本来只需要+2就行了，现在还得-7，反倒是增加步数了。因此要把这些数放到圆上，每个数都有可能是“中位数”，要遍历这些所谓的“中位数”，找与所有值距离最短的
- 破环成链的要点
首先是要确定圆上有一个边是不会通过的，所以可以从这个边上把圆给剪开，让圆变成一条直线。常用的方法是在直线终点之后再把前面的拷贝一遍，这样原本圆上的任何一个起点到终点绕一圈的组合都能在直线上面找到。而这道题把后面的数都加上m，因为前面的数本来就是模之后出来的，后面再加上m既可以保证单调，又不会影响加减的次数，也就是不影响相对距离

求距离和最短的$\displaystyle O(1)$的公式

#include <iostream>
#include <algorithm>

using namespace std;

const long long N = 4e5 + 10;

long long n, m, t;
long long a[N];
long long s[N];
long long ans;

int main()
{
    cin >> t;

    while (t--)
    {
        ans = 1e18 + 10;
        cin >> n >> m;

        for (long long i = 1; i <= n; i++)
        {
            cin >> a[i];
            a[i] %= m;
        }

        sort(a + 1, a + n + 1);

        for (long long i = 1; i <= n; i++)
            a[i + n] = a[i] + m;
        for (long long i = 1; i <= n * 2; i++)
            s[i] = s[i - 1] + a[i];

        for (long long i = 1; i <= n; i++)
        {
            long long l = i, r = l + n - 1, mid = r + l >> 1;
            long long left = (mid - l + 1) * a[mid] - (s[mid] - s[l - 1]);
            long long right = (s[r] - s[mid]) - (r - mid) * a[mid];
            ans = min(ans, left + right);
        }

        cout << ans << '\n';
    }

    return 0;
}