题解 P1128 【[HNOI2001]求正整数】

· · 题解

@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;
}