暴力搜索即可。
显然变换过程中数一定变小,记忆化搜索即可。
显然如果 nnn 中存在除了 2,3,52,3,52,3,5 的其他质因子,必定无解。
考虑三种变换的实质。
操作 111:去掉当前数中的 111 个质因子 222。
操作 222 :将当前数中的质因子 222 增加 111 个,去掉当前数中的 111 个质因子 333。
操作 333 :将当前数中的质因子 222 增加 222 个,去掉当前数中的 111 个质因子 555。
那么做法就出来了,一个质因子 222 贡献为 111,质因子 333 贡献为 222,质因子 555 贡献为 333。
复杂度 O(Tlogn)\mathcal{O}(T\log n)O(Tlogn)。
使用您的 Hydro 通用账户