T0907 快递批次(deliv)

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        ll total = 0, mx = 0;
        for (ll &v : a) {
            cin >> v;
            total += v;
            mx = max(mx, v);
        }

        // 总数为 0：所有批次本来就是 0，一次合并都不用
        if (total == 0) {
            cout << 0 << "\n";
            continue;
        }

        // 最终每组的包裹数 d 必须整除 total，且 d >= 最大的那一批
        vector<ll> divisors;
        for (ll d = 1; d * d <= total; d++) {
            if (total % d == 0) {
                divisors.push_back(d);
                if (d != total / d) divisors.push_back(total / d);
            }
        }
        sort(divisors.begin(), divisors.end());

        int answer = n - 1;
        for (ll d : divisors) {
            if (d < mx) continue;
            ll k = total / d;
            // 前缀和必须恰好在 d, 2d, ..., (k-1)d 处切一刀
            ll sum = 0, need = d;
            int cnt = 0;
            bool ok = true;
            for (ll v : a) {
                sum += v;
                if (sum == need) {
                    cnt++;
                    need += d;
                } else if (sum > need) {
                    ok = false;
                    break;
                }
            }
            if (ok && cnt == k) {
                answer = n - (int)k;
                break;
            }
        }

        cout << answer << "\n";
    }
    return 0;
}