考虑枚举最终的列数，显然固定列数检查答案时间复杂度是 \Theta\!\left(n\right)。

枚举时进行一个简单的剪枝：从 m 开始分别向左右枚举列数，保证列数始终小于当前最优解。

正确性显然。考虑复杂度：

首先答案至多为 \left\lfloor\frac nm\right\rfloor。所以向左枚举的数量至多为 \min\!\left(m-1,\left\lfloor\frac nm\right\rfloor-1\right)，最坏情况此值为 \Theta\!\left(\sqrt n\right)。

向右枚举同理

故最坏时间复杂度为 \Theta\!\left(n\sqrt n\right)。

#include <climits>
#include <iostream>
using namespace std;

int n;
int m;
int k;

int a[200000];

int res;

int Change(int base) {
    int res = INT_MAX;
    for (int i = 0; i < base; i++) {
        int cur = 0;
        for (int j = i; j < n; j += base) {
            if (a[j] != k) {
                cur++;
            }
        }
        res = min(res, cur);
        if (res == 0) {
            return 0;
        }
    }
    return res;
}

void Solve() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    res = INT_MAX;
    for (int i = m; i > 0 && m - i < res; i--) {
        res = min(res, m - i + Change(i));
        // cout << res << endl;
    }
    for (int i = m + 1; i - m < res; i++) {
        res = min(res, i - m + Change(i));
        // cout << res << endl;
    }
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        Solve();
    }
}
// 64 位输出请用 printf("%lld")