题目重述

给定初始值 $x$，目标值 $y$，以及操作上限 $k$。每次操作可以：

• 选择 $1 \le a \le k$，执行 $x = x \times a$
• 选择 $1 \le a \le k$，执行 $x = x / a$（必须整除）

求最少操作次数，若不可能则输出 $-1$。

---

核心思路

1. 问题分解

设 $g = \gcd(x, y)$，令：

$$x = g \cdot x', \quad y = g \cdot y'$$

其中 $\gcd(x', y') = 1$。

关键观察：由于乘除操作保持数的因子结构，且 $\gcd(x', y') = 1$，要使得 $x$ 变为 $y$，必须：

1. 先将 $x'$ 通过除法操作变为 $1$（去除所有与 $y'$ 不匹配的因子）
2. 再将 $1$ 通过乘法操作变为 $y'$（添加 $y'$ 所需的因子）

因此：

$$\text{答案} = f(x', k) + f(y', k)$$

其中 $f(n, k)$ 表示将 $n$ 变为 $1$ 的最少操作次数（只使用除法操作），若不可能则为 $-1$。

证明可行性：因为 $\gcd(x', y') = 1$，$x'$ 和 $y'$ 没有公共质因子。任何从 $x'$ 到 $y'$ 的路径都必须经过 $1$，否则无法消去 $x'$ 独有的因子。而乘法操作只会增加因子，不能直接得到与 $x'$ 互质的 $y'$。

---

2. 子问题定义

对于任意正整数 $n$，定义：

$$f(n, k) = \min\{ \text{步数} \mid \text{通过不断除以不超过 } k \text{ 的因子，将 } n \text{ 变为 } 1 \} $$

为什么只考虑除法？

• 除法操作能减少数值，符合“化简”的需求
• 乘法操作只会让数值变大，不利于到达 $1$
• 最优策略中，在化简阶段只使用除法，在构造阶段只使用乘法（对称性）

---

3. 动态规划求解 $f(n, k)$

设 $n$ 的所有因子为：

$$d_1 = 1 < d_2 < d_3 < \dots < d_m = n$$

定义 $dp[i]$ 表示将 $d_i$ 变为 $1$ 的最小操作次数。

转移方程：

$$dp[i] = \min_{\substack{j < i \\ d_i \bmod d_j = 0 \\ d_i / d_j \le k}} (dp[j] + 1) $$

解释：

• 从 $d_i$ 出发，除以 $a = d_i / d_j$（必须满足 $a \le k$ 且 $a$ 是整数）
• 一步到达 $d_j$
• 再从 $d_j$ 到 $1$ 需要 $dp[j]$ 步

边界条件：

$$dp[1 \text{对应的索引}] = 0$$

最终结果：

$$f(n, k) = dp[m] \quad (\text{若 } dp[m] \text{ 为无穷大，则返回 } -1) $$

---

4. 复杂度优化

如果对 $1$ 到 $n$ 所有数都做 DP，复杂度为 $O(n^2)$，不可接受（$n \le 10^6$）。

关键优化：$f(n, k)$ 只依赖于 $n$ 的因子，而不需要所有中间数。

因子个数上界：

• $10^6$ 以内的数，最多有约 $240$ 个因子（例如 $720720$ 有 $240$ 个因子）
• 一般来说，$d(n) = O(n^{1/3})$

因此：

• 枚举所有因子：$O(\sqrt{n})$
• DP 状态数：$d(n) \le 240$
• 每次转移枚举 $j$：$O(d(n))$
• 总复杂度：$O(\sqrt{n} + d(n)^2) \approx O(10^3 + 240^2) \approx 6 \times 10^4$，完全可行

实现细节：

// 枚举 n 的所有因子
for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        divs.push_back(i);
        if (i != n / i) divs.push_back(n / i);
    }
}
sort(divs.begin(), divs.end());

DP 循环优化： 由于因子已排序，$d_i / d_j$ 随 $j$ 减小而增大。当 $d_i / d_j > k$ 时，更小的 $j$ 只会使商更大，因此可以提前退出：

for (int i = 1; i < n; i++) {
    for (int j = i - 1; j >= 0; j--) {
        if (divs[i] / divs[j] > k) break;  // 提前退出
        if (divs[i] % divs[j] == 0) {
            dp[i] = min(dp[i], dp[j] + 1);
        }
    }
}

---

算法步骤总结

对于每个测试用例 $(x, y, k)$：

1. 计算 $g = \gcd(x, y)$
2. 令 $x' = x / g$，$y' = y / g$
3. 计算 $a = f(x', k)$，$b = f(y', k)$
4. 若 $a = -1$ 或 $b = -1$，输出 $-1$；否则输出 $a + b$

其中 $f(n, k)$ 的实现：

• 找出 $n$ 的所有因子，排序
• 初始化 $dp$ 数组，$dp[0] = 0$，其余为一个大数（如 $100$）
• 按因子升序进行 DP 转移
• 返回 $dp[\text{last}]$，若仍为大数则返回 $-1$

---

时间复杂度

• 每个测试用例：$O(\sqrt{\max(x', y')} + d(x')^2 + d(y')^2)$
• $x' \le 10^6$，$d(n) \le 240$
• 最坏情况约 $10^3 + 2 \times 240^2 \approx 1.2 \times 10^5$ 次操作
• $t \le 10^4$ 但保证 $\sum x$ 和 $\sum y \le 10^8$，实际总复杂度可接受

---

示例验证

样例 1: $x=4, y=6, k=3$

• $g = \gcd(4,6) = 2$
• $x' = 2, y' = 3$
• $f(2,3)$：因子 $[1,2]$，$dp[1]=dp[0]+1=1$
• $f(3,3)$：因子 $[1,3]$，$dp[1]=1$
• 答案 $= 1+1 = 2$

样例 2: $x=4, y=5, k=3$

• $g = 1$
• $x' = 4, y' = 5$
• $f(4,3)$：因子 $[1,2,4]$，可从 $4 \to 2 \to 1$，需要 $2$ 步
• $f(5,3)$：因子 $[1,5]$，$5$ 无法除以 $\le 3$ 的因子（除了 $1$），无法到达 $1$，返回 $-1$
• 答案 $-1$

样例 4: $x=10, y=45, k=3$

• $g = \gcd(10,45) = 5$
• $x' = 2, y' = 9$
• $f(2,3) = 1$（$2 \to 1$，除以 $2$）
• $f(9,3)$：因子 $[1,3,9]$，$9 \to 3 \to 1$，需要 $2$ 步
• 答案 $= 1+2 = 3$

---

正确性证明

1. 必要性：由于 $\gcd(x', y') = 1$，任何从 $x'$ 到 $y'$ 的路径必须消去 $x'$ 的所有质因子（否则无法与 $y'$ 互质），因此必须经过 $1$。
2. 最优性：在化简阶段，除法操作是最有效的减少方法；在构造阶段，乘法操作是最有效的增加方法。由于操作可逆且步数对称，分别计算再相加得到最优解。
3. 可行性：$f(n, k)$ 的 DP 正确计算了最少除法步数，因为每一步只能除以不超过 $k$ 的因子，且 DP 枚举了所有可能的中间状态（$n$ 的所有因子）。

---

注意事项

1. 边界情况：当 $x = y$ 时，$g = x$，$x' = y' = 1$，$f(1,k)=0$，答案为 $0$。
2. 无解情况：若 $x'$ 或 $y'$ 有大于 $k$ 的质因子且该质因子的幂次无法通过多次除法消除，则无解。
3. 整除判断：注意 $d_i \bmod d_j = 0$ 的条件，确保除法操作合法。
4. 循环顺序：第二层循环从大到小遍历并提前退出，利用了因子排序的单调性。