HNOI2001 求正整数

发表于 | 分类于 |
字数统计: 380 字

题目链接

题解

一看就是DP
按质因数DP，转移的时候保存一下指数即可。
对了，还要加上对数的优化。直接保存一个巨大的整数不是什么容易的事。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
using namespace std;
typedef long long ll;
double f[20][50005],P_[20];
int F[20][50005]={0},n,P[17]={1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int real_ans[50005]={0};
int multiply_to_int(int s1[],int s2){
    int i,j,x=0;
    for(i=1;i<=s1[0];i++)
        x+=s1[i]*s2,
        s1[i]=x%10000,x/=10000;
    while(x)
        s1[++s1[0]]=x%10000,x/=10000;
}
int main(){
    scanf("%d",&n);
    int i,j,k,mini,cnt;
    double m,ans;
    for(i=0;i<20;i++)
        for(j=0;j<=n;j++)
            f[i][j]=1e9;
    for(i=0;i<=16;i++)
        P_[i]=log(P[i]);
    for(i=1;i<=n;i++)
        f[1][i]=(i-1)*P_[1],F[1][i]=1;
    for(i=1;i<=15;i++)
        for(j=1;j<=n;j++)
            for(k=1;j*k<=n;k++){
                m=f[i][j]+(k-1)*P_[i+1];
                if(m<f[i+1][j*k])
                    f[i+1][j*k]=m,F[i+1][j*k]=j;
            }            
    for(ans=1e9,i=1;i<=16;i++)
        if(ans>f[i][n])
            ans=f[i][n],mini=i;
    real_ans[0]=real_ans[1]=1;
    for(j=mini,k=n;j>0;j--){
        cnt=k/F[j][k];
        for(i=1;i<cnt;i++)
            multiply_to_int(real_ans,P[j]);
        k=F[j][k];
    }
    printf("%d",real_ans[real_ans[0]]);
    for(i=real_ans[0]-1;i>=1;i--)
        printf("%04d",real_ans[i]);
    printf("\n");
    return 0;
}