2016 ICPC大连站---F题 Detachment

时间:2022-05-02 11:03:51

题意:输入一个x,将x拆分成一些小的数(这些数不能相同,即x=a1+a2+......   ai!=aj when i!=j),然后这些数相乘得到一个成积(s=a1*a2*......),求最大的乘积s;

思路:考虑最简单的做法便是贪心,很明显将一个数分的越小,这个乘积越大,那么对于给的x 先找2+3+4+....+n<=x 找到最大的n  如果和小于x ,那么将n右移一个数(n->n+1)  如果和还小于x继续将n-1右移......知道和x相等时,输出s   这样做时间复杂度很高,那么得优化。 由上面的过程分析发现,2+3+...+n<=x &&2+3+...+n+(n+1)>x

那么x-(2+3+...+n)<=n  那么最终x分成的数结果只有三种情况:x=2+3+...+(k-1)+(k+1)+...+n+(n+1)     x=3+4+...+n+(n+1)    x=3+4+...+(n-1)+n+(n+2)

其实第一种和第二种情况相同。 分析过程如上,详细计算过程如下:2+3+...+n<=x  所以n*(n+1)<=2*x+2   n<=sqrt(2*n+2)

代码如下:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
using namespace std;
typedef long long LL;
const LL mod=1e9+;
const LL maxn=1e5+;
LL A[maxn],s[maxn];
LL Inv[maxn];
void getINV()///逆元;
{
Inv[]=;
for(LL i=; i<maxn; i++)
Inv[i] = (mod-mod/i)*Inv[mod%i]%mod;
}
void init()
{
s[]=;
for(LL i=;i<maxn;i++)
s[i]=s[i-]+i;
A[]=;
for(LL i=;i<maxn;i++)
A[i]=A[i-]*i%mod;
getINV();
} int main()
{
init();
int T;
cin>>T;
while(T--)
{
int pos;
LL x,sum;
scanf("%lld",&x);
LL n=(LL)(sqrt(*x+));
for(int i=n;i>=;i--)
if(s[i]<=x){
pos=i;
break;
}
if(x==) { puts(""); continue; }
if(s[pos]==x) { printf("%lld\n",A[pos]); continue; }
if(s[pos]+pos->=x){
LL tot=s[pos]+pos--x;
sum=(A[pos+]*Inv[tot+])%mod;
}
else{
LL tot=s[pos+]-+pos--x;
sum=((A[pos+]*Inv[])%mod)*Inv[tot+]%mod;
}
printf("%lld\n",sum);
}
return ;
}