2016年ACM/ICPC大连赛区 F题（思维+二分+逆元）
题意：
给你一个数n(n<=1e9)，让你把n拆成若干个不相同的数的和，且这些数的积是所有拆分方法中最大的。输出这些数的最大积对1e9+7取模。
思路：一看就是直接O(1)或O(logn)求出答案。因为T给了1e6。
计算一下对每个数而言，拆的数有没有他。枚举一下前几项，发现除了至多一个数之外，其他的所有数都是连续的时积最大。且1对答案是没有任何贡献的，最少从2开始。
因此如果n可以拆成2+3+4+...+l的形式时，答案就是l的阶乘。
如果2+3+4+...+l刚好比n多1，我们不难发现去掉2和l，加上l+1时答案最大。
如果2+3+4+...+l刚好比n多x(x>=2)，我们不难发现去掉x时，答案最大。
但是TLE。。。 预处理一下阶乘，再处理一下逆元即可。
代码：
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fLL
using namespace std;
const int maxn=100010;
const ll mo=1e9+7;
ll n,m,k;
ll ans,tmp,cnt;
bool jud(ll mid)
{
return ((mid*(mid+1)/2-1)>=n);
}
ll power(ll a,ll n) //a的n次方mod
{
ll ans=1;
a=a%mo;
while (n)
{
if(n&1) ans=(ans*a)%mo;
n>>=1;
a=(a*a)%mo;
}
return ans;
}
ll yu[maxn];
int main()
{
yu[0]=1;
for(int i=1;i<maxn;i++)
yu[i]=(yu[i-1]*i)%mo;
int T,cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
if(n<=4) {printf("%lld\n",n);continue;}
ll l=0,r=n;
while(l<r)
{
ll mid=(l+r)>>1;
if(jud(mid)) r=mid;
else l=mid+1;
}
l=r;
ans=1;
tmp=(r*(r+1)/2-1);
if(tmp==n)
{
ans=yu[l];
printf("%lld\n",ans);
continue;
}
l--;
if(tmp==n+1)
{
//cout<<l<<" "<<endl;
ans=yu[l];
ans=ans*power(2,mo-2)%mo;
ans=(ans*(l+2))%mo;
printf("%lld\n",ans);
}
else
{
ans=yu[l+1];
ans=ans*power(tmp-n,mo-2)%mo;
printf("%lld\n",ans);
}
}
return 0;
}