——挺综合的一道题，题目大意是给你一个数字N，让你切割成多个数字，求如何切割使得得到的数字的最小公倍数最大，首先得知道如何求最小公倍数：将s分割为a和b，则lcm(a,b)=a*b/gcd(a,b)。可知，如果gcd(a,b)>1则，lcm(a,b)至少要除以2，而如果a和b互质，则gcd为1，得到的结果最优。所以，最优的策略是将N分割成若干互质的数字，便可得到最大的最小公倍数。同时应知，1和任何自然数互质。两个不同的质数互质。一个质数和一个合数，这两个数不是倍数关系时互质。不含相同质因数的两个合数互质。对于一个质数x和其的任意倍数nx，其lcm为nx*x/x=nx，白白浪费了x这部分，所以对于一个质数和其倍数，只能选择一个，这就变成分组背包，一组只能选一个。 ——由于lcm结果过大会溢出，题目要求的结果有取模，但如果在递推dp的过程中取模，在比较选择最优结果时就会出错，例如模数为m，上一次求出dp[k]=m+1，结果取模得1，下一次随便一个大于1得答案就会覆盖掉正确答案。但是不取模就会溢出，肯定也会造成答案错误。这里使用了取log来保存答案，dp改使用double类型的，原本选取了一个数字a，dp[j]=dp[j-a]*a,取log之后，因为log（ab）=loga+logb;所以变成了，dp[j]=dp[j-a]+log(a);然后用另一个数组储存取模之后得答案。
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<cmath>using namespace std;int n, m;int PRim[1000];bool noprim[3005];double dp[3005];//质数相乘变成取对数后相加log(a*b)=loga+logbint ans[3005];int primnum = 0;void init(){ for (int i = 2; i <= 3000; i++){ if (noprim[i] == 0){ prim[primnum++] = i; for (int j = i*i; j <= 3000; j += i){ noprim[j] = 1; } } }}int main(){ init(); while (~scanf("%d%d", &n, &m)){ memset(dp, 0, sizeof(dp)); for (int i = 0; i <= n; i++)ans[i] = 1; for (int i = 0; i < primnum&&prim[i] <= n; i++){ double cnt = log(prim[i] * 1.0); for (int j = 3000; j >= prim[i]; j--){ for (int k = 1, p = prim[i]; p <= j; p *= prim[i], k++){ if (dp[j - p] + cnt*k > dp[j]){ dp[j] = dp[j - p] + cnt*k; ans[j] = ans[j - p] * p % m; } } } } printf("%d/n", ans[n]); } return 0;}新闻热点
疑难解答
