「COCI 2023.3」Logaritam

ID: 3367

传统题

1000ms

256MiB

尝试: 3

已通过: 1

难度: 10

上传者:

姜君豪

标签>

2023

COCI

题意理解

我们有一个对数序列 $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$ 。

关键性质

对数序列的结构
由 $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$
所以整个序列由所有质数位置的值决定。
约束关系
如果 $xy \le n$ ，那么 $a_x$ 和 $a_y$ 的值会约束 $a_{xy}$ 。
反过来，如果 $a_{xy}$ 固定了，那么 $a_x$ 和 $a_y$ 必须满足 $a_x + a_y = a_{xy}$ 。
一个位置被固定
假设 $x_i$ 被固定为某个值（不是原来的值），那么所有形如 $a_u + a_v = a_{x_i}$ 的约束（其中 $uv = x_i$ ）都会限制 $a_u$ 和 $a_v$ 。
同时， $x_i$ 也会出现在其他约束中作为 $u$ 或 $v$ 。

问题转化

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

节点： $1 \dots n$ 中所有出现在某些 $xy \le n$ 中的数（其实所有 $\le n$ 的数都是节点）。
边：对于 $uv \le n$ ，有一条边连接 $u$ 和 $v$ ，表示 $a_u + a_v = a_{uv}$ 。

当 $x_i$ 固定时，这个等式会沿着图传播，从而确定某些变量的值或关系。

分析 $x_i$ 固定的影响

设 $x_i$ 固定为某个值 $c$ （未知，但我们知道它不等于原来的值）。

对于所有 $u, v$ 满足 $u v = x_i$ ，有： [ a_u + a_v = c ] 如果 $u = v$ ，则 $2 a_u = c$ ，所以 $a_u = c/2$ （如果 $c$ 不是偶数可能出问题？这里 $a$ 可以是实数，所以没关系）。
对于所有 $u, v$ 满足 $u x_i = w \le n$ ，有： [ a_u + c = a_w ] 所以 $a_w - a_u = c$ 。
对于所有 $u, v$ 满足 $v x_i = w \le n$ ，有： [ c + a_v = a_w ] 所以 $a_w - a_v = c$ 。

这些约束会传播到整个图。

连通分量

实际上，如果我们把每个约束 $a_u + a_v = a_{uv}$ 看作连接 $u$ 和 $v$ 的边（无向边？注意不是直接连接 $u$ 和 $v$ ，而是连接 $u, v, uv$ 三个点？）
更准确地说，我们可以把每个约束 $a_u + a_v = a_{uv}$ 看作一个三元关系，可以表示为： [ a_u + a_v - a_{uv} = 0 ] 这是一个线性方程。

所有这样的方程构成一个线性系统。
变量是 $a_1, \dots, a_n$ ，但 $a_1 = 0$ 已知。

当 $x_i$ 固定时，就增加了一个方程 $a_{x_i} = c$ （ $c$ 未知但固定）。

自由变量与最小修改

初始时（没有固定 $x_i$ ），自由变量的个数等于质数的个数（因为每个质数位置的值可以任意取，然后所有合数位置由质数决定）。

当我们固定 $a_{x_i}$ 时，可能会减少自由变量的个数。

关键：
我们要求的是，在固定 $a_{x_i}$ 后，最少改动多少个其他位置的值，使得序列满足所有约束。

“改动”意味着我们可以任意设置该位置的值（覆盖原来的值），但 $x_i$ 不能改。

图论建模

把每个约束 $a_u + a_v = a_{uv}$ 看作连接 $u, v, uv$ 的三个点在一个等式关系中。
实际上，我们可以建一个图，节点是 $1 \dots n$ ，对于每个 $uv \le n$ ，在 $u, v, uv$ 之间添加一条“超边”？这样不好处理。

更常见的做法（类似数论函数）：
考虑 $b_x = a_x - a_1$ 之类的变换，但 $a_1=0$ 所以 $b_x = a_x$ 。

已知结论

这类问题有一个已知的图论模型：

构造图 $G$ ：顶点集 $V = \{1, 2, \dots, n\}$
对于每个 $uv \le n$ ，添加边 $(u, v)$ ，权值关系是 $a_u + a_v = a_{uv}$ 。

其实更准确是：每个 $uv \le n$ 定义了一个三角形约束： $a_u + a_v = a_{uv}$ 。

我们可以把它看作一个线性系统：
每个约束 $a_u + a_v - a_{uv} = 0$ 。

系统矩阵的行对应每个 $(u,v)$ 对，列对应 $a_1 \dots a_n$ 。

固定一个变量后的影响

固定 $a_{x_i} = c$ 后，某些变量会被确定（如果它们与 $x_i$ 在约束中连通）。

我们可以用并查集或DFS找出所有受影响的变量。

最小修改数 = 初始自由变量个数 - 固定 $x_i$ 后仍然自由的变量个数？
不对，因为我们可以选择改某些位置的值来满足约束。

其实问题等价于：
在约束图中，固定 $x_i$ 后，某些变量会被线性确定。我们要选择最少的变量（除了 $x_i$ ）进行赋值，使得整个系统有解。

这相当于在依赖图中找最小点覆盖？不对。

实际做法

找出所有质数 $p \le n$ ，它们初始是自由变量。
固定 $x_i$ 后，用 BFS/DFS 从 $x_i$ 出发，沿着约束 $a_u + a_v = a_{uv}$ 传播，标记所有被确定的变量。
如果出现矛盾（比如一个变量被要求等于两个不同的值），则输出 -1。
否则，最少修改数 = 初始自由变量数 - 新自由变量数？
这里要小心：我们允许改动其他位置的值，所以其实是在固定 $x_i$ 后，剩下的自由变量可以任意设置，但必须保证所有约束满足。
如果固定 $x_i$ 后，系统仍然有自由变量，我们可以不改它们；如果没有自由变量但系统有解，我们不需要改任何其他位置；如果没有自由变量且无解（不可能，因为我们可以改其他位置的值来满足？）

仔细想：
固定 $x_i$ 后，系统可能无解（如果 $x_i$ 的新值与某些约束冲突）。
但我们可以通过改动其他位置的值来消除冲突。

所以问题变成：在固定 $x_i$ 的情况下，找到最少的变量集合 $S$ （不含 $x_i$ ），使得给这些变量任意赋值后，整个系统有解。

这等价于：固定 $x_i$ 后，约束图可能分成若干连通分量，每个连通分量的变量由其中一个自由变量决定。
我们需要选择最少的变量（除了 $x_i$ ）来覆盖所有连通分量？不对。

已知解法（结论）

这个题在 COCI 原题中，解法是：

对数序列由所有质数位置的值唯一确定。
固定 $x_i$ 后，所有与 $x_i$ 在“约束图”中连通的变量都会被确定。
最少修改数 = （与 $x_i$ 连通的变量个数） - 1（因为 $x_i$ 已经固定，不算在修改内，但我们要改其他连通位置的值来满足约束）。

具体步骤：

对每个 $x_i$ ，找出所有在约束关系中受 $x_i$ 影响的变量集合 $C$ 。
如果 $1 \in C$ 且 $x_i \ne 1$ ，则输出 -1（因为 $a_1$ 必须为 0，如果 $x_i$ 固定为非 0 且影响 $a_1$ 则矛盾）。
否则，输出 $|C| - 1$ 。

如何找 $C$

$C$ 包含所有能通过约束关系 $a_u + a_v = a_{uv}$ 从 $x_i$ 到达的变量。

可以从 $x_i$ 开始 BFS：

状态：当前变量 $u$
对于每个 $u$ ，找所有 $v, w$ 满足 $u v = w \le n$ ，把 $v$ 和 $w$ 加入集合。
对于每个 $u$ ，找所有 $v, w$ 满足 $v w = u \le n$ ，把 $v$ 和 $w$ 加入集合。

这样 BFS 直到没有新变量。

时间复杂度

直接 BFS 对于 $n \le 10^8$ 太大。
需要更高效的方法：
我们只需要考虑 $x_i$ 的因子和倍数，以及它们的因子和倍数，等等。
实际上 $C$ 是 $x_i$ 的“因子倍数闭包”，可以用数论方法枚举。

代码框架

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

int n, q;

// 找与 x 在约束关系中连通的变量个数
int get_size(int x) {
    set<int> vis;
    queue<int> q;
    q.push(x);
    vis.insert(x);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        // 枚举 u 的因子 v，则 w = u/v 也在约束中
        for (int v = 1; v * v <= u; v++) {
            if (u % v == 0) {
                int w = u / v;
                if (v <= n && w <= n) {
                    if (!vis.count(v)) { vis.insert(v); q.push(v); }
                    if (!vis.count(w)) { vis.insert(w); q.push(w); }
                }
            }
        }
        // 枚举 u 的倍数 w，则 v = w/u 也在约束中
        for (int w = u; w <= n; w += u) {
            int v = w / u;
            if (v <= n) {
                if (!vis.count(v)) { vis.insert(v); q.push(v); }
                if (!vis.count(w)) { vis.insert(w); q.push(w); }
            }
        }
    }
    return vis.size();
}

int main() {
    cin >> n >> q;
    while (q--) {
        int x;
        cin >> x;
        if (x == 1) {
            // a1 必须为 0，如果固定 a1 则可能矛盾
            // 如果 a1 被改过，则无法满足 a1=0 除非改回来，但题目不能改 x_i
            cout << -1 << "\n";
            continue;
        }
        int cnt = get_size(x);
        // 如果 1 在连通分量里且 x != 1，则矛盾
        // 检查 1 是否在连通分量中
        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;
            for (int v = 1; v * v <= u; v++) {
                if (u % v == 0) {
                    int w = u / v;
                    if (v <= n && w <= n) {
                        if (!vis.count(v)) { vis.insert(v); qq.push(v); }
                        if (!vis.count(w)) { vis.insert(w); qq.push(w); }
                    }
                }
            }
            for (int w = u; w <= n; w += u) {
                int v = w / u;
                if (v <= n) {
                    if (!vis.count(v)) { vis.insert(v); qq.push(v); }
                    if (!vis.count(w)) { vis.insert(w); qq.push(w); }
                }
            }
        }
        if (has_one) {
            cout << -1 << "\n";
        } else {
            cout << cnt - 1 << "\n";
        }
    }
    return 0;
}

总结

本题的关键是：

理解对数序列的约束结构（ $a_{xy} = a_x + a_y$ ）
将约束视为图，固定 $x_i$ 会传播影响
判断是否与 $a_1=0$ 矛盾
最小修改数 = 受影响变量数 - 1

算法标签
数论 约束传播 BFS 因子倍数图

#L3952. 「COCI 2023.3」Logaritam