不一样的解法。
写完一看，标签里不是有 dp 吗，居然没人写。来提供一个动规做法。
本文中的 \(x\) 和 \(n\) 都是指输入的 \(x\) 和 \(n\)。\(\operatorname{set}_i\) 表示 \(i\) 的各位数字的集合，如 \(\operatorname{set}_{998244353} = \{2,3,4,5,8,9\}\)。
先考虑暴力 dp：
\(f_i\) 表示得到数 \(i\) 的最小操作次数，转移平凡，\(f_{i\times k}\gets\min(f_{i\times k},f_i+1)\)，其中 \(k\in\operatorname{set}_i\)。
最后答案就是所有 \(n\) 位数的最小 \(f\) 值。
状态数过多，不能通过。
首先明确我们不会乘 \(0\) 或 \(1\)，因为 \(0\) 会把自己搞没，\(1\) 浪费操作次数。
那么到操作过程中的所有数都可以表示为:
压缩一下：\(num=x\cdot2^a\cdot3^b\cdot5^c\cdot7^d\)（其他乘数均可用 \(2,3,5,7\) 表示）。
所以只有可以被写成这个形式的数才可能得到。这样就压缩了状态量。
自然地，\(f_{a,b,c,d}\) 表示得到 \(x\cdot2^a\cdot3^b\cdot5^c\cdot7^d\) 的最小次数。范围是 \(10^{19}\)，所以 \(a<64,b<40,c<28,d<23\)。
\(160\) 万左右的状态数，可过。转移几乎和暴力转移一样的，刷表即可。
设 \(v\) 为 \(10^n\)，时间复杂度 \(\Theta(\log_2v\cdot\log_3v\cdot\log_5v\cdot\log_7v\cdot n)\)，约 \(3\times10^7\) 次运算。
31ms 被 bfs 吊打（