解题思路:
【题意】
给定一个自然数x，让你给出一种拆分方式x=a1+a2+...(ai≠aj)，使得每个小部分的乘积s=a1*a2*...最大
【类型】 贪心构造 【分析】
此题关键在于得出如何能使乘积s最大
按照以往经验，必然是取一段连续自然数能够使得乘积最大，而这段连续自然数可从2开始(为啥不从1开始?从1开始还不如将这个1给这段连续自然数的最后一个数)，于是我们可以得到形如2+3+4+...+k(k=2,3,...)的式子，而x是10^9内的任意整数，我们不可能恰好能够凑成连续自然数之和，可能会多出△x
而这个△x的值，我可以保证它的范围为0≤△x≤k，相信大于等于0还是好理解的，为什么会小于等于k呢?因为当它大于k时，原式不是可以增加一项?即2+3+4+...+k+(k+1)
那么多出来的△x怎么处理呢?显然是从后往前均摊给连续自然数中的(k-1)个数，为啥从后往前?因为若我们从前往后，总是会使连续自然数重复，不好处理
于是，在我们分配完△x之后，我们大致会得到下述两种式子:
①2*3*...*(i-1)*(i+1)*...*k*(k+1)
②3*4*...*i*(i+1)*...*k*(k+2)
显然，我们要计算此结果，可以借助阶乘，而阶乘中缺失的项，我们除掉就可以了，那么便会涉及除法取模，显然需要用到乘法逆元
做法讲解完毕，以下是为什么连续段乘积最大的大概证明:
简而言之，假如有一个数让你拆成两个要求积最大，肯定是拆成两个一样的，如果拆成n个，肯定就是拆成这个数/n，如果没说几个，肯定都拆成2，比如10,5*5=25,2^5=32.这个题要求不能一样的，所以肯定就是2,3,4这样排列了，从2开始让它变小，这样数量会最多，每次加一就是让他越来越接近。所以用前缀和记录，如果有剩余的话，肯定是从后往前逐个+1，而且剩余的那个数最多=2,3,4...最大的那个数，举个例子会发现有两种情况：1.比如2*3*4*5余下5，相等。最优就是3*4*5*7，就是每个数都加一遍，然后会剩下一个1，加给最后一个，总的来说就是 除以2，乘上t+2,（t是最后一个数的值）；2.不相等，2,3,4,5，余2，最优就是2,3,5,6，就是用3的阶乘*6的阶乘除以4的阶乘，因为数量太多，不能一个一个乘，就用前缀积相除，数字太大，就要用逆元了。。然后用二分优化下。。 这题找到贪心策略后，要知道数据量大的话要用前缀积+逆元求，用前缀和优化找余数。。二分也是优化这个的
#include<bits/stdc++.h> #define max 1000000000 #define MOD (1000000007LL) //const __int64 MOD=1000000007;//不能用define定义MOD否则会出错，define是一个函数 using namespace std; __int64 f[45000]; int sum[45000]; int inv[45000]; void del() { inv[1]=1;f[1]=1;sum[1]=0; for (int i = 2; i<45000; i++) { inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;///乘法逆元 f[i]=(f[i-1]*i)%MOD;///前缀乘（在取余MOD的环境下，配合后面的乘法逆元） sum[i]=sum[i-1]+i;///前缀和（从2开始） } //printf("%d %d %d xxx\n",inv[2],inv[3],inv[1]); return; } int main() { int T,n,k,l,r,mid; __int64 ans; del(); while(~scanf("%d",&T)) { while(T--) { scanf("%d",&n); if(n<5)printf("%d\n",n); else { l=2;r=45000;mid=(l+r)>>1; while(l+1<r) ///二分查找 { if(sum[mid]>n) r=mid,mid=(r+l)>>1;///r定义为开，不取状态 else l=mid,mid=(r+l)>>1;///l定义为闭，取状态 } k=n-sum[l];///printf("%d %d %d xx",sum[l],k,inv[l+1-k]); if(2+k>l) ans=f[l]*inv[2]%MOD*(k+2)%MOD,printf("%I64d\n",(ans+MOD)%MOD); else ans=f[l]*inv[l+1-k]%MOD*(l+1)%MOD,printf("%I64d\n",(ans+MOD)%MOD); } } } return 0; } 代码参考： here
参考网址：here andhere
