L Clock Master(2020 China Collegiate Programming Contest Weihai Site)补题

题意：给你一个数b,求ans = b1 * b2 * b3 …最大,且b = b1+b2+b3…
其实就是求b1 ,b2, b3, b4 的最小公倍数的最大值。
思路：
任意一个数都可以质因数分解成
N = p1^a1 * p2^a2 * p3^a3…

所以我们可以这样来想这个问题
j将b看成是一个容量为b的背包；p1^a1, p2^a2,p3^a3…不同的质数的不同次方看成是分成了一个组；这就是一个分组背包的问题了，从质数组中去选择，它们的和不超过b，求它们乘积的最大值。
注意：
①数据范围较大，需要将二维的dp优化为一维的dp
②数据较大，用log进行优化，打表进行处理
log(a*b) =log a + log b，所以状态转移方程为：

③用欧拉筛求出30010以内的素数。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 30010;
int primes[maxn];
bool vis[maxn];
int cnt;
double dp[maxn];
double logg[maxn];
//欧拉筛素数
void get_prime(){
	for(int i = 2;i <= maxn;i++){
		if(!vis[i]){
			primes[++cnt] = i;
		}
		for(int j = 1;primes[j] * i <= maxn;j++){
			vis[i*primes[j]] = true;
			if(i % primes[j]==0){
				break;
			}
		}
	}
	/*
	for(int i = 1;i<=cnt;i++){
	  cout<<primes[i]<<" ";
	}
	*/
} 
//打表,避免数据过大 
void init(){
	for(int i = 1;i <= maxn;i++){
		logg[i] = log(i);
	//	cout<<logg[i]<<" "; 
	}
	for(int i = 1;i <= cnt;i++){//选择的物品 (质数)
			for(int j = maxn;j >= primes[i];j--){//背包大小 
				for(int k = primes[i];k <= j ;k *= primes[i]){//物品幂次的选择 
					dp[j] = max(dp[j],dp[j-k] + logg[k]);
				     //不选择质数          选择质数（幂次） 
				}
			}
		}
}
int main(){
	get_prime();
	init();
	int t,b;
	cin>>t;
	while(t--){
		cin>>b;
		cout<<fixed<<setprecision(9)<<dp[b]<<endl;
	}
	return 0;
}

(有什么错误就指出来吧hhh…)