逆元+前缀积+STL二分
这题做了挺久了，考察的东西还挺多，而且还是一道思维题。
原题链接：HDU - 5976
华师男和他女票又创造了一个新的游戏 他们一起想一个数x，然后对这个进行拆分成任意多个 各不相同的数， a1,a2,a3 … 满足(x= a1+a2+a3+…) 他们决定齐心协力找到一种拆分方法，使得所有这些数的乘积最大。
Input
第一行有一个整数T，表示有T组测试数据。 随后T行，每行都有一个数字x。 1≤T≤10^6, 1≤x≤10^9
Output
先获取乘积的最大值，再对其模10^9+7后输出。
Sample Input
2 4 5
Sample Output
4 6
Hint
4 = 4 5 = 2 + 3，2*3 = 6
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
typedef long long ll;
ll num[100005],top=1,ans[100005],ni[100005];
void init()
{
num[top]=1;
ans[top]=1;
ni[top]=1;
ll i,now=0,mul=1;
for(i=2; now<=1000000000; i++)
{
now+=i;
num[++top]=now; //前缀和
mul=mul*i%mod;
ans[top]=mul; //前缀积
ni[i]=(mod-mod/i)*ni[mod%i]%mod; //逆元
}
}
int main()
{
init();
ll t;
scanf("%lld",&t);
while(t--)
{
ll x;
scanf("%lld",&x);
ll s=lower_bound(num+1,num+1+top,x)-num;
if(num[s]==x)
{
printf("%lld\n",ans[s]);
}
else
{
s--;
ll need=x-num[s],re=ans[s];
if(need==s)
{
re=re*ni[2]%mod;
re=re*(s+2)%mod;
}
else
{
re=re*ni[s+1-need]%mod;
re=re*(s+1)%mod;
}
printf("%lld\n",re);
}
}
return 0;
}尽量将X拆成2+3+4……+k，如果x恰好能拆成，则答案就是k！如果x拆完还剩t，则将X拆为2+3+……+(k-t) + (k–t+2)+(k–t+3)+……+k+(k+1);通过预处理可以得出(k+1)!只需乘上（k – t + 1）的逆元。
此外有个特例，如果减到最后剩下的数和最后一个数一样大，多出来的一就加在最后一个数上面。
PS：原来一般的数组也可以用STL二分。。。
附上逆元的公式 (要求MOD为素数):
int[] inv = new int[MAXN];
inv[1] = 1;
for (int i = 2; i<MAXN; i++)
inv[i] = inv[MOD%i]*(MOD-MOD/i)%MOD;更多关于逆元的知识: http://blog.csdn.net/xwxcy/article/details/51493193
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-08-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读