hdu 5646 拆数积最大 数学

将一个数拆开，然后求乘积

hdu 5646

1. 拆成若干实数

利用柯西不等式以及对 x1/x $x^{1/x}$求极值点

2. 拆成若干整数

3 与 e较为接近，所以选择3，然后不足的选择2

3. 拆成k个整数

首先 t=n%k $t=n\%k$ ,k个数里面有 t 个 是[n/k] + 1,k-t个 [n/k];

4. 拆成k个不相同的整数

方案如下
1. 如果能拆成 2，3，4，5，..n这样连续的，就直接这样拆
2. 如果，拆成 2，3，4，5，…… n,剩余t，0

 LL n,k;
LL Binary(LL nn)
{
    LL l = k,r = 1e9;
    while(r>=l)
    {
        LL mid = (r+l)>>1;
        if(mid*(mid+1)/2 - (mid-k)*(mid-k+1)/2 > nn)
            r = mid-1;
        else
            l = mid+1;
    }
    return r;
}
int main(void)
{

    int T;
    cin>>T;
    while(T--)
    {

        cin>>n>>k;
        if(n<k*(k+1)/2)
        {
            printf("-1\n");
            continue;
        }
        LL t = Binary(n);
        LL ans = 1;
        if(n == t*(t+1)/2-(t-k)*(t-k+1)/2)
        {
            for(LL i = t-k+1; i <= t; ++i)
                ans = ans*i%mod;
            cout<<ans<<endl;
        }
        else
        {
            LL tmp = n - t*(t+1)/2 + (t-k)*(t-k+1)/2;
            for(LL i = t-k+1; i <= t; ++i)
                ans = ans*(i + (i > t-tmp?1:0)) %mod;
            cout<<ans<<endl;
        }


    }
    return 0;
}

相关问题 ，整数拆分求中类，组合数学