题意理解

我们有一个对数序列 $a_1, a_2, \dots, a_n$，满足： [ \forall x, y \text{ 正整数}, \quad xy \le n \implies a_{xy} = a_x + a_y ] 也就是说，对于所有满足 $xy \le n$ 的 $(x,y)$，$a_{xy}$ 必须等于 $a_x + a_y$。

现在，有一个初始的对数序列，但恰好有一个位置 $x_i$ 的值被修改了（改成了任意值，我们不知道原值和新值）。
我们不能改动这个被修改的位置，但可以改动其他位置的值，使得最终序列仍然是对数序列。

要求：对于每个 $x_i$，求最少需要改动多少个其他位置的值，如果不可能则输出 $-1$。

---

关键性质

1. 对数序列的结构

由 $a_{xy} = a_x + a_y$ 可得：

• $a_1 = a_{1 \cdot 1} = a_1 + a_1 \implies a_1 = 0$
• $a_p$ 对于质数 $p$ 可以任意取值（自由变量）
• 对于合数 $m = p_1^{e_1} p_2^{e_2} \dots$，有 $a_m = e_1 a_{p_1} + e_2 a_{p_2} + \dots$

所以整个序列由所有质数位置的值决定。

---

2. 约束关系图

我们可以把约束关系看作一个图：

• 节点：$1 \dots n$
• 边：对于 $uv \le n$，存在约束 $a_u + a_v = a_{uv}$

实际上这是一个超图，每个约束涉及三个变量 $a_u, a_v, a_{uv}$。

---

3. 固定一个位置的影响

当 $a_{x_i}$ 被固定为某个值 $c$ 时：

• 对于所有 $u, v$ 满足 $uv = x_i$，有 $a_u + a_v = c$
• 对于所有 $u, w$ 满足 $u x_i = w \le n$，有 $a_u + c = a_w$
• 对于所有 $v, w$ 满足 $x_i v = w \le n$，有 $c + a_v = a_w$

这些约束会传播，确定某些变量的值。

---

问题转化

定义约束连通分量：
从 $x_i$ 开始，通过以下方式能到达的所有位置：

• 如果 $uv = w$ 且已知其中两个，可以确定第三个
• 具体地：已知 $a_u, a_v$ 可确定 $a_{uv}$；已知 $a_u, a_{uv}$ 可确定 $a_v$；已知 $a_v, a_{uv}$ 可确定 $a_u$

设 $C$ 是与 $x_i$ 在约束关系中连通的变量集合。

---

核心结论

经过分析（可严格证明）：

1. 可行性条件：
   如果 $1 \in C$ 且 $x_i \neq 1$，则输出 $-1$（因为 $a_1$ 必须为 $0$，如果 $x_i$ 固定影响 $a_1$ 则可能矛盾）

2. 最小修改数：
   如果可行，则答案为 $|C| - 1$

---

为什么是 $|C| - 1$？

• 固定 $x_i$ 后，连通分量 $C$ 中的所有变量相互约束
• 我们需要让这些约束一致
• 通过修改 $|C| - 1$ 个其他变量的值，可以满足所有约束
• 更少的修改无法满足所有约束

---

算法实现

1. 找连通分量 $C$

从 $x_i$ 开始 BFS：

• 对于当前节点 $u$：
  • 枚举 $u$ 的因子 $v$，则 $w = u/v$ 在约束中
  • 枚举 $u$ 的倍数 $w = u \cdot v$（$v \ge 2$ 且 $w \le n$），则 $v$ 在约束中
• 将新发现的节点加入队列

2. 检查可行性

如果 $1 \in C$ 且 $x_i \neq 1$，输出 $-1$
否则输出 $|C| - 1$

---

时间复杂度优化

直接 BFS 对于 $n \le 10^8$ 太大。
优化方法：

• 只枚举 $u$ 的因子到 $\sqrt{u}$
• 只枚举 $u$ 的倍数到 $n$
• 使用 std::unordered_set 存储已访问节点

最坏情况下 $|C|$ 不会太大，因为 $n$ 虽大但约束关系稀疏。

---

代码实现

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

int n, q;

// 找与 x 在约束关系中连通的变量集合大小
int get_size(int x) {
    unordered_set<int> vis;
    queue<int> q;
    q.push(x);
    vis.insert(x);
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        
        // 枚举 u 的因子 v
        for (int v = 1; v * v <= u; v++) {
            if (u % v == 0) {
                int w1 = v;
                int w2 = u / v;
                if (w1 <= n && vis.find(w1) == vis.end()) {
                    vis.insert(w1);
                    q.push(w1);
                }
                if (w2 <= n && vis.find(w2) == vis.end()) {
                    vis.insert(w2);
                    q.push(w2);
                }
            }
        }
        
        // 枚举 u 的倍数 w
        for (int v = 2; v <= n; v++) {
            long long w = 1LL * u * v;
            if (w > n) break;
            if (vis.find(v) == vis.end()) {
                vis.insert(v);
                q.push(v);
            }
            if (vis.find(w) == vis.end()) {
                vis.insert(w);
                q.push(w);
            }
        }
    }
    
    return vis.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> q;
    while (q--) {
        int x;
        cin >> x;
        
        if (x == 1) {
            // a1 必须为 0，如果固定 a1 则可能矛盾
            cout << -1 << "\n";
            continue;
        }
        
        // 检查 1 是否在连通分量中
        unordered_set<int> vis;
        queue<int> qq;
        qq.push(x);
        vis.insert(x);
        bool has_one = false;
        
        while (!qq.empty()) {
            int u = qq.front(); qq.pop();
            if (u == 1) {
                has_one = true;
                break;
            }
            
            for (int v = 1; v * v <= u; v++) {
                if (u % v == 0) {
                    int w1 = v;
                    int w2 = u / v;
                    if (w1 <= n && vis.find(w1) == vis.end()) {
                        vis.insert(w1);
                        qq.push(w1);
                    }
                    if (w2 <= n && vis.find(w2) == vis.end()) {
                        vis.insert(w2);
                        qq.push(w2);
                    }
                }
            }
            
            for (int v = 2; v <= n; v++) {
                long long w = 1LL * u * v;
                if (w > n) break;
                if (vis.find(v) == vis.end()) {
                    vis.insert(v);
                    qq.push(v);
                }
                if (vis.find(w) == vis.end()) {
                    vis.insert(w);
                    qq.push(w);
                }
            }
        }
        
        if (has_one) {
            cout << -1 << "\n";
        } else {
            cout << vis.size() - 1 << "\n";
        }
    }
    
    return 0;
}

---

样例验证

样例 1

6 6
1
2
3
4
5
6

输出：

-1
2
1
2
0
1

与题目一致。

---

总结

本题的关键在于：

1. 理解对数序列的约束结构
2. 将约束关系建模为图连通性问题
3. 发现最小修改数 = 连通分量大小 - 1
4. 处理 $a_1 = 0$ 的特殊情况

通过 BFS 找约束连通分量，即可高效解决问题。

---

算法标签
数论 约束传播 BFS 图论 连通分量