2020CCPC Weihai Site L.Clock Mater 数论,背包
题意
抽象出来就是给定(n),构造出最大的(LCM(x_1 * x_2 *x_3....))且(x_1 + x_2 + x_3 ... = n)
[1leq T leq 30000\
1leq b leq 30000
]
对答案输出用(ln(ans))
分析
考虑最后加起来的(x),肯定希望这些数互质,这样就要求每个数唯一分解后形如(p^alpha)
由于题给的范围比较小,所以我们希望能枚举所有指数的情况,这个时候就用分组背包即可
价值即(log(x))
复杂度(O(n^2logn))
注意点:计算每个数的对数有太多不必要的时间,可以预处理出(ln)值
赛时没做出这题,实在是不应该
代码
const int maxn = 1e5 + 5;
int cnt;
int prime[maxn];
int vis[maxn];
void euler_sieve() {
cnt = 0;
for (int i = 2; i <= maxn; i++) {
if (!vis[i]) {
prime[++cnt] = i;
}
for (int j = 1; j <= cnt; j++) {
if (i * prime[j] > maxn) break;
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
double dp[30010];
double lg[30010];
const int M = 30010;
void init() {
for (int i = 0; i < M; i++)
lg[i] = log(i);
for (int i = 1; i <= cnt; i++)
for (int j = M - 1; j >= prime[i]; j--)
for (int k = prime[i]; k <= j; k *= prime[i])
dp[j] = max(dp[j], dp[j - k] + lg[k]);
}
void solve() {
int n = rd();
printf("%.10f
", dp[n]);
}
int main() {
euler_sieve();
init();
int T = rd();
while (T--)
solve();
}