——挺綜合的一道題，題目大意是給你一個數字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;}新聞熱點
疑難解答
