HDU 3092
题目大意
将一个数 (s) 写成很多数相加，求这些数的 (lcm) 最大
(\)
(\)
(Solution)
网上的题解我真是emm？？？直接复述一遍结论就离谱。这道题重点难道不是在发现这个结论吗？完全背包谁不会啊？？忍不住吐槽了kkk
首先一定要手玩几个例子，比如 (10) 分解为 (5 + 3 + 2)，(11) 分解为 (5 + 3 + 2 + 1)，发现都是质数
如果是在考试中，再多打几个表看看是不是这样，然后就可以直接写了，但是是在做题的话还是来理解一下
一个前置证明，若 (a > 1, b > 1) 且 (a, b) 都为正整数，那么 (a * b = c) ，这个还是比较显然
假设 (s) 分解为了 (a + b)，且 (a, b) 都为非质数，那么有 $$a * b = a_1 * a_2 * ... * a_i * b_1 * b_2 * ... * b_j (a_1, a_2, ..., a_i, b_1, b_2, ..., b_j都为质数)$$
把 (a + b) 质因数分解后贡献的答案一样，但用的和还少一些，所以拆分成质数的是最佳的
还有两个要注意的点
(1.) 质数的次幂也是可以选的。
为什么呢？还是看上面那个证明，若 (b = c^x) ，(c) 为一个质数，那么这时候是没有必要拆开 (b) 的，因为拆成一样的之后 (operatorname{lcm}) 就多了一个 (b^y)
(2.) 由于公倍数可能会很大，所以要取模。
但是取了模怎么比较大小呢？这时候就要用到 (log) 来帮忙了
为什么选 (log) ？因为 (log n) 可以把 (n) 变为一个很小的数，且若 (a * b < c * d) ，满足 (log a + log b < log c + log d)
也就是说，在不改变数字相对大小的情况下，把数字缩小了。(有点儿像用精度换取了空间？不知道有没有人能get到
具体实现看代码8
(\)
完结撒花✿✿ヽ(°▽°)ノ✿
（感觉这篇题解写得好严肃啊233不是我的风格啊～果然数学到哪都令我头秃呢（雾
(\)
(\)
(Code)
#include<bits/stdc++.h>
#define ll long long
#define F(i, x, y) for(int i = x; i <= y; ++ i)
using namespace std;
int read();
const int N = 2e4 + 5;
int n, mod, prime[N], vis[N];
double dp[N];
ll ans[N], lans;
void init()
{
F(i, 2, N - 1)
{
if(! vis[i]) prime[++ prime[0]] = i;
for(int j = 1; j <= prime[0] && prime[j] * i <= N - 1; ++ j)
vis[prime[j] * i] = 1;
}
}
int main()
{
init();//欧拉筛找质数
while(scanf("%d%d", &n, &mod) != EOF)
{
F(i, 0, n) dp[i] = 0, ans[i] = 1;
for(int i = 1; i <= prime[0] && prime[i] <= n; ++ i)
for(int j = n; j >= prime[i]; -- j)
for(int k = 1, now = prime[i]; now <= j; ++ k, now *= prime[i])//枚举 prime[i] 的 k 次方
{
if(now <= j && dp[j - now] + log(now) > dp[j])
dp[j] = dp[j - now] + log(now), ans[j] = ans[j - now] * now % mod;//dp 用来找答案，ans 用来存真的答案
}
printf("%lld
", ans[n]);
}
return 0;
}
/*--------------- Bn_ff 2020.7.4 HDU3092 ---------------*/
int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}