难度：提高+/省选-
不算难，但是思想挺有意思的一题。

题目描述

        对于任意输入的正整数n，请编程求出具有n个不同因子的最小正整数m。
        例如：n=4，则m=6，因为6有4个不同整数因子1,2,3,6；而且是最小的有4个因子的整数。

输入格式

        $n(1≤n≤50000)$

输出格式

        $m$

题解

        题意非常明确。
        首先贪心是不对的，虽然它大部分情况下正确。正解其实是个DP。通过一些合理的猜测（？，$m$包含的质因子种类不会很多，并且一定是前几个质因子（因为要最小），取前20个足够。
        然后开始$DP$。规定$dp(x,y)$为取前$y$个质因子，有$x$个因子的最小数值，那么有状态转移方程：

        这个方程主要是基于下面的原理：将某一个数分解成$p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}$形式后，它的因子数目为：

        所以转移方程就可以列出了，它其实就是最后一个质因子指数的枚举。
        但是$n$比较大，这会使最终结果位数很多，需要高精度。如果$DP$转移时就带上高精度去计算和比较，复杂度会爆炸。于是有一个新奇思路是给$dp$取对数，通过对数来计算和比较。这样的话，根据对数的运算法则，可以得到下面的方程：

        结果按理取一个$exp$就行，但是它没法套高精。于是开一个数组记录转移的方向，最后用高精度计算最终答案即可。因为乘数很小，可以$O(n)$地高精乘。
        复杂度$O(n\sqrt n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>

using namespace std;
vector<int> vvp[50005];
const int P[] = {
        0, 2, 3, 5, 7, 11,
        13, 17, 19, 23, 29,
        31, 37, 41, 43, 47,
        53, 59, 61, 67, 71
};
int n;
double dp[50005][30], lg[30];
int ans[100005], at, to[50005][30];

inline void mul(int s) {
    for (int i = 0; i < at; i++)ans[i] *= s;
    int nxt = 0, tp;
    for (int i = 0; i < at; i++) {
        tp = (nxt + ans[i]) % 10;
        nxt = (nxt + ans[i]) / 10;
        ans[i] = tp;
    }
    while (nxt != 0)ans[at++] = nxt % 10, nxt /= 10;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                vvp[i].push_back(j);
                if (j * j != i)vvp[i].push_back(i / j);
            }
        }
    }
    for (int i = 1; i <= 20; i++)lg[i] = log(P[i]);
    for (int i = 1; i <= n; i++)dp[i][1] = (i - 1) * lg[1], to[i][1] = i;
    for (int i = 2; i <= 20; i++) {
        for (int j = 1; j <= n; j++) {
            double minn = 1e50, tmp;
            for (int s:vvp[j]) {
                tmp = dp[j / s][i - 1] + (s - 1) * lg[i];
                if (tmp < minn)minn = tmp, to[j][i] = s;
            }
            dp[j][i] = minn;
        }
    }
    ans[0] = at = 1;
    for (int i = 20, now = n; i >= 1; i--) {
        for (int j = 1; j < to[now][i]; j++)mul(P[i]);
        if (i > 1)now = now / to[now][i];
    }
    for (int i = at - 1; i >= 0; i--)putchar(ans[i] + '0');
}