2016 ICPC大連站---F題 Detachment，icpc---f

2016 ICPC大連站---F題 Detachment，icpc---f

題意：輸入一個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+7;
const LL maxn=1e5+5;
LL A[maxn],s[maxn];
LL Inv[maxn];
void getINV()///逆元;
{
    Inv[1]=1;
    for(LL i=2; i<maxn; i++)
        Inv[i] = (mod-mod/i)*Inv[mod%i]%mod;
}
void init()
{
    s[1]=0;
    for(LL i=2;i<maxn;i++)
       s[i]=s[i-1]+i;
    A[0]=1;
    for(LL i=1;i<maxn;i++)
        A[i]=A[i-1]*i%mod;
    getINV();
}

int main()
{
    init();
    int T;
    cin>>T;
    while(T--)
    {
        int pos;
        LL x,sum;
        scanf("%lld",&x);
        LL n=(LL)(sqrt(2*x+2));
        for(int i=n;i>=1;i--)
        if(s[i]<=x){
            pos=i;
            break;
        }
        if(x==1) { puts("1"); continue; }
        if(s[pos]==x) { printf("%lld\n",A[pos]); continue; }
        if(s[pos]+pos-1>=x){
            LL tot=s[pos]+pos-1-x;
            sum=(A[pos+1]*Inv[tot+2])%mod;
        }
        else{
            LL tot=s[pos+1]-2+pos-1-x;
            sum=((A[pos+2]*Inv[2])%mod)*Inv[tot+3]%mod;
        }
        printf("%lld\n",sum);
    }
    return 0;
}