P1128 [HNOI2001]求正整数

传送门

rqy是我们的红太阳没有它我们就会死

可以考虑dp，设\(dp[i][j]\)表示只包含前\(j\)个质数的数中，因子个数为\(i\)的数的最小值是多少，那么有转移方程

\[f[i][j]=min(f[i/k][j-1]\times p_j^{k-1})
\]

这玩意儿肯定是不能高精dp的……于是看到乘法就想到对数……根据对数的基本定理，有

\[log\ n=\sum c_i\ log\ p_i
\]

那么我们可以改一下转移

\[f[i][j]=min(f[i/k][j-1]+ (k-1)log\ p_j)
\]

然后算出最后的答案之后倒着找一下转移的方向高精乘回去就是了

因为没有写eps于是调了一个小时都找不出错我再也不偷懒不写eps了QAQ

//minamoto

#include<bits/stdc++.h>

#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)

using namespace std;

const double min(const double &x,const double &y){return x<y?x:y;}

const int p[]={

   2,  3,  5,  7, 11,

  13, 17, 19, 23, 29,

  31, 37, 41, 43, 47,

  53, 59, 61, 67, 71

};double Log[25],f[505][25];int d[505],n,tot,len,A[100005],pos;

void mul(int x){

	int add=0;

	fp(i,1,len)A[i]=A[i]*x+add,add=A[i]/10,A[i]%=10;

	while(add)A[++len]=add%10,add/=10;

}

int main(){

//	freopen("testdata.in","r",stdin);

	scanf("%d",&n);fp(i,1,n)if(n%i==0)d[++tot]=i;

	fp(i,0,19)f[0][i]=0;fp(i,0,19)Log[i]=log(p[i]);

	fp(i,2,tot){

		fp(k,0,19)f[i][k]=1e9;

		fp(j,1,i-1)if(d[i]%d[j]==0){

			int t=d[i]/d[j];

			fp(k,1,19)f[i][k]=min(f[i][k],f[j][k-1]+Log[k-1]*(t-1));

		}

	}A[1]=len=1;

	fp(i,0,19)if(f[tot][i]<f[tot][pos])pos=i;

	for(register int i=tot,nxt;i>1;i=nxt,--pos){

		for(nxt=1;d[i]%d[nxt]||f[i][pos]<f[nxt][pos-1]+Log[pos-1]*(d[i]/d[nxt]-1)-1e-5;++nxt);

//		for(nxt=1;d[i]%d[nxt]||f[i][pos]<f[nxt][pos-1]+Log[pos-1]*(d[i]/d[nxt]-1)-1e-5;++nxt);

		fp(k,1,d[i]/d[nxt]-1)mul(p[pos-1]);

	}

	while(len--)printf("%d",A[len+1]);return 0;

}

巴特西

P1128 [HNOI2001]求正整数

最新文章

热门文章