专门出的一个搜索题。

我们考虑$dfs(i,x,y,now)$。

此处$i$表示该考虑第$i$个质数的归属了，当前分别是$x,y$，当前一共有$now$个不同的质因子。

那么下一次$dfs$肯定是$dfs(i+1,x\times p[i]^t,y,now+1)$，或者是$dfs(i+1,x,y\times p[i]^t,now+1)$，或者是$dfs(i+1,x,y,now)$。

需要注意的是，这个过程中如果写法不太好，很容易乘爆$long\ long$，要么用$int128$，要么用除法来保证不会乘爆，比如if (a*b<=n)可以改写乘if (a<=n/b)。

但这么做会常数巨大，可以考虑分别用两个$long\ long$去存当前$x,y$乘以那个质数的幂以后的结果，如果超了$n$就当$n+1$即可。这样全程不用除法。

剪枝的话很容易想到，就是假设后面都用第$i,i+1,...,$种质数，加上当前的$now$都凑不够目前的$best$，那就直接不用搜了。