题意简述

给定一个序列 $a_i$，每次操作可以让序列中一个元素加一或者减一，求让所有元素减去某个数 $x$ 之后同余 $m$。

题解思路

我们不妨转换一下题意，题目要求我们让所有元素 $a_i - x$ 对 $m$ 同余，我们可以改写每个元素的表达式为 $a_i = k \times m + p_i$，假设令所有元素同余 $m$ 为 $Z$，则有 $a_i - x \equiv Z \pmod m$，代入展开得到 $Z = p_i - x$。也就是说，题意要让所有元素的 $p_i - x$ 相等，而 $x$ 是固定的，实际上我们其实就是要操作让所有的 $p_i$ 相等。

因此问题简化成了，给定一个序列 $p_i$，每次可以让 $p_i$ 加一或者减一，求让所有元素相等的最小操作次数，而是一个经典的题型，只需要将序列从小到大排序后取中位数(中点)就好。然而本题的难点正在于此，由于问题是建立在同余下的，因此可能存在形如样例的，$m=9$，让元素 $a_i = 8$ 变成 $3$ 可以通过 $(a_i+4) \bmod 9$ 得到，这比直接减去5更加优秀。那么我们再次发现，实际上，对于在 $\bmod m$ 的数的加和减，我们可以看成是在一个长度为 $m$，从 $0$ 到 $m-1$ 的环形上做移动。那么我们延续之前的思路，要取中位数作为目标值，而在环上，每个数都可以作为中位数，我们只需要枚举这个中位数，每次计算出这个中位数对应的答案，最后取最小就好。

一些细节的处理：

• 对于环来说，统计信息较为困难，我们可以考虑利用常见的破换成链的技巧，将序列 $a_i$ 拷贝一份接在后面，形如 $a_1 a_2 a_3 \cdots a_n a_1 a_2 \cdots a_n$，这样我们从 $i$ 枚举到 $n$，其中区间 $[i,i+n-1]$ 就是一个环对应的区间了。

• 对于枚举到的中点 $p$，如何快速计算所有点到 $p$ 的距离之和，假设中点为 $p$，可以考虑将距离之和分成两部分：

• 1. 在 $p$ 之前的点到 $p$ 的距离为 $\sum_{i<p} a_p - a_i$
• 1. 在 $p$ 之后的点到 $p$ 的距离之和为 $\sum_{i>p} a_i - a_p$

     由于公式中的 $a_p$ 是常数，我们可以将它提到求和符号的外面，则 $\sum_{i<p} a_p - a_i = i \times p - \sum_{i<p} a_i$，同理 $\sum_{i>p} a_i - a_p = \sum_{i>p} a_i - (i + n - p - 1) \times p$，其中 $\sum_{i<p} a_i$ 对应 $a_i$ 的区间和 $[1,p-1]$，同理 $\sum_{i>p} a_i$ 对应 $a_i$ 的区间和 $[p,i+n-1]$，可以直接用前缀和维护。

• 由于存在同余关系，对于后面一段拷贝的区间，在计算距离的时候应该特殊考虑，例如计算 $a_{n+1}$ 到 $a_n$ 的距离，应该是 $m + (a_{n+1} - a_n)$，其他对于跨两个区间计算的也同理，注意到 $m$ 是一个常数，因此在拷贝后续区间 $a_{n+1} \sim a_{2n}$ 时，可以手动为其都加上 $m$，这样计算距离时就规避了分类讨论。

时间复杂度：$O(n \log n+n)$。

AC CODE

#include <bits/stdc++.h>
using namespace std;
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
using i64 = long long;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<i64> a(2 * n + 1), presum(2 * n + 1);
    for (int i = 1; i <= n; i++) // 求出pi
        cin >> a[i], a[i] %= m;
    sort(a.begin() + 1, a.begin() + n + 1); // 排序
    for (int i = 1; i <= n; i ++) // 拷贝时加上偏移量m
        a[i + n] = a[i] + m;
    for(int i = 1; i <= 2 * n; i ++)
        presum[i] = presum[i - 1] + a[i];
    i64 ans = 1e18;
    for(int i = 1; i <= n; i ++)
    {
        int p = i + n / 2; // 当前区间[i,i+n]的中点
        i64 w = (p - i) * a[p] - presum[p - 1] + presum[i - 1] 
                + presum[i + n - 1] - presum[p] - (i + n - 1 - p) * a[p]; // 公式在上面
        ans = min(ans, w);
    }
    cout << ans << '\n';
}

signed main()
{
    IOS;
    int _ = 1;
    cin >> _;

    while (_--)
        solve();

    return 0;
}