这题做了挺久了，考察的东西还挺多，而且还是一道思维题。
原题链接：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
代码如下：
代码语言：javascript复制#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("%lldn",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("%lldn",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为素数):
代码语言：javascript复制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
