本文共 964 字，大约阅读时间需要 3 分钟。

转化题意后就是给定$n$,要求分配成若干个数

使这些数字的最小公倍数最大

显然分配的数字是质数最好,所以可以对每个质数$x$当作物品来选

但是对于一个质数$x$,我们可以选$x$,也可以选$x^2,x^3....$

所以这是一个分组背包问题,暴力转移即可

#include 
   
    using namespace std;const int mx = 3e4;const int maxn = 2e6+10;int vis[maxn],prime[maxn],top;void make_prime(){
   	for(int i=2;i<=mx;i++)	{
   		if( !vis[i] )	prime[++top] = i;		for(int j=1;j<=top && prime[j]*i<=mx;j++)		{
   			vis[prime[j]*i] = 1;			if( i%prime[j]==0 )	break;		}	}}double f[2][mx+10],LN[mx+10];int id;int main(){
   	make_prime();	int t; cin >> t;	for(int i=1;i<=30000;i++)	LN[i] = log(i);	for(int i=1;i<=top;i++)	{
   		int t = i&1, v = t^1;		for(int u=0;u<=30000;u++)	f[t][u] = f[v][u];				for(int j=prime[i];j<=30000;j*=prime[i] )		for(int u=j;u<=30000;u++)			f[t][u] = max( f[t][u],f[v][u-j]+LN[j] );			}//	for(int i=1;i<=30000;i++)//		f[top&1][i] = max( f[top&1][i],f[top&1][i-1] );	while( t-- )	{
   		int n; cin >> n;		printf("%.10lf\n",f[top&1][n] );	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/117093156 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！