题解[HNOI2001] 求正整数

P1221 最多因子数

根据唯一分解定理 $m=p_1^{a_1}\times p_2^{a_2} \times ... \times p_k^{a_k}$.

那么 $m$ 的约数个数就为 $(a_1+1)(a_2+1)...(a_k+1)$.

并且观察数据范围, $n \le 5 \times 10^4$.

那么可以得出 $k \le 16$ ,因为 $2^{16} \ge 5 \times 10^4$.

所以接下来就可以直接通过搜索枚举前16个质数的幂次方 $a$ 就行了.

但是由于答案可能很大,所以要用高精,但如果每一次更新答案都用一次高精,很明显会超时.

根据小学知识 $\lg(x\times y)=\lg{x}+\lg{y},lg{x^y}=y\times \lg{x}$,我们可以对答案取一个对数,就不怕答案很大了

接下来就可以开始通过搜索来枚举 $a_i$了

直接爆搜肯定是不行的,所以要想办法优化一下,我们在dfs的时候传入四个参数

$poi$ 表示当前枚举到第 $poi$ 个质数, $now$ 表示当前的质因子个数, $last$ 表示之前枚举的幂次方, $temp$ 表示当前答案取完对数的结果

可以得到两个明显的剪枝

最优性剪枝:如果当前的 $temp$ 已经大于之前的最小值,直接返回

可行性剪枝:在枚举幂次方 $i$ 时, 如果 $(i+1) \times now$不是$n$的倍数,舍掉这种情况

并且在枚举的时候,我们需要从 $last$ 开始,因为枚举出来的 $a_i$ 一定时单调不上升的,否则答案一定不是最优,因为我们始终可以交换任意两个 $a_i$ 使答案更小

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;

int prime[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
int rec[16], a[16], n;
double recv = 1e13, val[16];

struct num
{
    ll data[10005];
    num operator * (const int b) const
    {
        num c;
        memcpy(c.data, data, sizeof(data));
        for (int i = 1; i <= c.data[0]; i++)
            c.data[i] *= b;
        for (int i = 1; i <= c.data[0]; i++)
        {
            if (c.data[i] >= 10000)
            {
                c.data[i + 1] += c.data[i] / 10000;
                c.data[i] %= 10000;
            }            
        }
        ll &h = c.data[0];
        while (c.data[h + 1] > 0)
        {
            h++;
            c.data[h + 1] += c.data[h] / 10000;
            c.data[h] %= 10000;
        }
        return c;
    }
    void print()
    {
        printf("%lld", data[data[0]]);
        for (int i = data[0] - 1; i >= 1; i--)
        {
            if (data[i] <= 9)
                printf("000");
            else if (data[i] <= 99)
                printf("00");
            else if (data[i] <= 999)
                printf("0");
            printf("%lld", data[i]);           
        }
 
    }
} ans;//高精乘

void dfs(int poi, int now, int last, double temp)
{
    if (poi == 16 || temp > recv || n % now)
        return;
    if (now == n)
    {
        if (temp < recv)
        {
            recv = temp;
            memcpy(a, rec, sizeof(rec));
        }
        return;
    }
    double t = val[poi];
    int k = n / now;
    for (int i = min(k - 1, last); i >= 0; --i)
    {
        rec[poi] = i;
        dfs(poi + 1, now * (i + 1), i, temp + i * t);
    }
    rec[poi] = 0;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < 16; i++)
        val[i] = log(prime[i]);
    dfs(0, 1, n - 1, 0);
    ans.data[0] = ans.data[1] = 1;
    for (int i = 0; i < 16; i++)
        while (a[i]--)
            ans = ans * prime[i];
    ans.print();
}