变形怪 题解

题意与关键信息

• 初始体型 $n$，$m$ 种配方 $x_1,\dots,x_m$。
• 每步：若 $v \bmod x_i = 0$，则 $v \to v / x_i$；可以变形任意多次（含 $0$ 次）。
• 求可达的不同体型数量（含初始体型）。
• 数据范围：$1 \le n \le 10^{18}$，$1 \le m \le 8$，$x_i \le 10^6$ 且两两不同。

从暴力到正解

暴力搜索（$n \le 10^3$，30 分）

DFS 枚举全部可达体型，用集合去重：

void dfs(ll v) {
    seen.insert(v);
    for (ll xi : x) if (v % xi == 0) dfs(v / xi);
}

$n$ 很小时状态数有限，可直接通过。$n$ 一大（如 $10^{18}$）状态可能爆炸？——并不会爆炸，见下。

特殊性质（$x_i$ 两两互质且 $x_i \mid n$、$x_i^2 \nmid n$，10 分）

记 $n$ 的质因数分解。因为 $x_i$ 两两互质且每个 $x_i$ 恰整除 $n$ 一次（$x_i^2 \nmid n$），每个配方一旦使用就会把 $n$ 中对应的那部分因子恰好除尽一次，之后该配方永远无法再用（$v$ 不再含 $x_i$ 的任何因子）。

于是每种配方只有"用 / 不用"两种选择，且互不干扰，答案恰为：

正解：BFS 去重

$v$ 能变到 $v/x_i$ 当且仅当 $x_i \mid v$。因为每一步都保持"整除"，所有可达体型都是 $n$ 的约数。$n \le 10^{18}$ 时约数个数最多约 $10^5$ 个，因此 BFS 状态数有限且很小：

unordered_set<ll> seen; queue<ll> q;
seen.insert(n); q.push(n);
while (!q.empty()) {
    ll v = q.front(); q.pop();
    for (ll xi : x)
        if (v % xi == 0 && seen.insert(v / xi).second)
            q.push(v / xi);
}
cout << seen.size();

复杂度

• 每个状态做 $m$ 次取模/除法，$O(1)$ 哈希判重。
• 状态数 $\le$ $n$ 的约数个数 $\le 10^5$，故 $O(m \cdot d(n))$，空间 $O(d(n))$。

易错点

1. long long：$n$ 可达 $10^{18}$，必须用 64 位整数。
2. $v = 1$ 时不可再变：$1 \bmod x_i = 1 \ne 0$，BFS 不会从 $1$ 继续扩展，天然终止。
3. 答案包含初始体型：$n$ 本身也要计数（入队前先 insert(n)）。
4. 配方可能永远用不上：$x_i \nmid n$ 时该配方无效（例如 $n$ 是质数时答案恒为 $1$），BFS 自然处理，无需特判。

参考代码

见 summercspj262B.cpp。