——挺綜合的一道題，題目大意是給你一個數字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);然后用另一個數組儲存取模之后得答案。