题目分析

给定 $N$ 个正整数 $a_1, a_2, \dots, a_N$，可以进行合并相邻数或拆分一个数的操作。
对于每个查询 $q$，求让所有数都等于 $q$ 的最小操作次数，若不可能则输出 $-1$。

---

核心思路

1. 问题转化

设总和 $S = \sum a_i$，最终要有 $k$ 个数，每个都是 $q$，则：

• 必要条件：$q$ 必须整除 $S$，即 $k = S / q$
• 操作次数 = 合并次数 + 拆分次数

2. 关键观察

操作次数公式：

• 最终数组长度 $k = S / q$
• 原数组中能直接作为 $q$ 的"完整段"数量 = $mp[q]$（预处理）
• 操作次数 = $(N - k) + (k - mp[q]) = N + k - 2 \cdot mp[q]$

其中：

• $N - k$：合并操作次数（从 $N$ 个数减少到 $k$ 个数）
• $k - mp[q]$：拆分操作次数（需要补充的 $q$ 的数量）

---

算法实现详解

1. 质因数分解与预处理

Miller-Rabin 素数测试 + Pollard's Rho

bool isPrime(u64 n);        // Miller-Rabin 确定性测试
u64 rho(u64 n);             // Pollard's Rho 分解
vector<pair<u64, int>> factorize(u64 n);  // 返回质因数分解

用于分解总和 $S$ 的所有质因数。

生成所有因数

vector<u64> all_divisors_from_pf(const vector<pair<u64, int>> &pf);

通过质因数分解生成 $S$ 的所有因数。

2. 核心预处理

前缀和与 GCD 统计

for (int i = 1; i <= n; i++)
    cin >> a[i], a[i] += a[i - 1];  // 计算前缀和

for (int i = 1; i <= n; i++)
    mp[__gcd(a[i], a[n])]++;  // 统计每个GCD值的出现次数

这里的关键：

• $a[i]$ 是前缀和，$a[n] = S$
• $\gcd(a[i], S)$ 表示从开头到 $i$ 的区间和与 $S$ 的最大公约数
• 这个 GCD 值能整除 $S$，是 $S$ 的因数

因数关系传播

for (auto it : pf) {
    ll p = it.first;
    for (auto x : d)
        if (a[n] % ((u128)x * p) == 0)
            mp[x] += mp[x * p];
}

这里用类似高维前缀和的方法：

• 如果 $x \cdot p$ 是 $S$ 的因数，那么所有能被 $x \cdot p$ 整除的前缀，也能被 $x$ 整除
• 因此 $mp[x]$ 应该包含 $mp[x \cdot p]$ 的计数

3. 查询处理

while (m--) {
    ll x;
    cin >> x;
    if (a[n] % x)  // x 不能整除总和
        cout << "-1\n";
    else {
        int tot = n - mp[x];  // 需要修改的位置数
        cout << tot + a[n] / x - (n - tot) << "\n";
    }
}

操作次数计算：

• $tot = n - mp[x]$：不能直接作为 $x$ 的段数
• $a[n] / x$：最终段数 $k$
• 操作次数 = $tot + k - (n - tot) = k + 2 \cdot tot - n$

---

复杂度分析

• 质因数分解：$O(S^{1/4})$ 使用 Pollard's Rho
• 生成所有因数：$O(d(S))$，其中 $d(S)$ 是因数个数
• 预处理：$O(n \log S + d(S) \cdot \omega(S))$，其中 $\omega(S)$ 是不同质因数个数
• 查询：$O(1)$ 每次

由于 $S \leq 10^{18}$，$d(S)$ 最多约 $10^5$ 量级，可接受。

---

算法标签

主要算法：

• 数论
• 质因数分解（Miller-Rabin + Pollard's Rho）
• 前缀和
• GCD 性质

相关技术：

• 高维前缀和思想
• 大数处理
• 查询优化

---

代码亮点

1. 高效质因数分解：使用确定性 Miller-Rabin 和 Pollard's Rho
2. GCD 统计技巧：通过 $\gcd(\text{前缀和}, S)$ 识别完整段
3. 因数关系传播：利用质因数关系高效计算 $mp$ 数组
4. 大数安全计算：使用 __uint128_t 避免溢出

---

总结

这道题通过数论和前缀和的巧妙结合，将操作次数计算转化为因数统计问题。核心在于识别原数组中能直接作为目标值 $q$ 的"完整段"，这通过 GCD 性质和质因数分解高效实现。算法充分利用了数论性质，实现了 $O(1)$ 查询的优秀复杂度。