自动搬运

查看原文

来自洛谷，原作者为

	_rqy **

搬运于2025-08-24 21:21:17，当前版本为作者最后更新于2018-02-25 20:44:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

@wangtianyi @天下第一剑客 这里是泥萌的错误及解决方案之一：

当输入为$8$的时候，答案应为$24 = 2^3*3$, 而非$30 = 2*3*5$。

既然贪心行不通，我们来考虑DP。 令$f_{i, j}$表示所有只包含前$j$个质因数的数中，因数个数为$i$的最小的数。

那么，根据因数个数公式

$$\tau(n)=\prod_i(k_i+1), \rm{where}\;n=\prod_i p_i^{k_i} $$

转移时枚举最后一个质因子的次数，我们有

$$f_{i, j} = \min_{k|i}\left(f_{\frac ik, j-1}p_j^{k-1}\right) $$

显然我们是不能高精dp的（随便输入了一个28493得到的答案有8577位十进制，想要高精dp的自己算算复杂度就好了）。那么考虑取对数，dp变成了

$$f_{i, j} = \min_{k|i}\left(f_{\frac ik, j-1}+(k-1)\log p_j\right) $$

最后要求结果的时候只要找到转移的方向把对应的$p_j^{k-1}$乘上去就好了。高精乘单精挺好写的。

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <map>
const int N = 50050;
const int p[20] = {
   2,  3,  5,  7, 11,
  13, 17, 19, 23, 29,
  31, 37, 41, 43, 47,
  53, 59, 61, 67, 71
};
double logp[20];
double f[505][20];
int d[505];
int cnt;
int A[100000], len;
void mul(int x) {
  int v = 0;
  for (int i = 0; i < len; ++i) {
    v = (A[i] = A[i] * x + v) / 10;
    A[i] %= 10;
  }
  while (v) A[len++] = v % 10, v /= 10;
}
int main() {
  int n, m = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) if (!(n % i)) d[m++] = i;
  for (int i = 0; i < 20; ++i) f[0][i] = .0;
  for (int i = 0; i < 20; ++i) logp[i] = log(p[i]);
  for (int i = 1; i < m; ++i) {
    for (int k = 0; k < 20; ++k)
      f[i][k] = 1e9;
    for (int j = 0; j < i; ++j) if (!(d[i] % d[j])) {
      int t = d[i] / d[j];
      for (int k = 1; k < 20; ++k)
        f[i][k] = std::min(f[i][k], f[j][k - 1] + logp[k - 1] * (t - 1));
    }
  }
  A[0] = len = 1;
  int j = 0;
  for (int i = 0; i < 20; ++i) if (f[m - 1][i] < f[m - 1][j]) j = i;
  for (int i = m - 1, nxt; i; i = nxt, --j) {
    for (nxt = 0; d[i] % d[nxt] || f[i][j] < f[nxt][j - 1]
        + logp[j - 1] * (d[i] / d[nxt] - 1) - 1e-5; ++nxt);
    for (int k = 1; k < d[i] / d[nxt]; ++k)
      mul(p[j - 1]);
  }
  while (len--) printf("%d", A[len]);
  return 0;
}