hdu 5646 DZY Loves Partition

最新推荐文章于 2020-09-14 10:13:41 发布

炎灸纹武

最新推荐文章于 2020-09-14 10:13:41 发布

阅读量487

点赞数

分类专栏：二分数学题文章标签： algorithm

本文链接：https://blog.csdn.net/Seraphimon/article/details/50978595

版权

数学题同时被 2 个专栏收录

9 篇文章

订阅专栏

二分

3 篇文章

订阅专栏

本文探讨了如何将一个给定的数n分解成k个数，使得这些数的乘积达到最大值。通过两种不同的方法实现了这一目标，包括直接减去已知序列和通过二分查找确定序列起始或结束位置的方法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5646

题意：给你一个数n，问你能否将其拆分成k个数，并使他们的乘积最大。

思路：讲N分成K个数，是的K个数的乘积最大。
那么这K个数有两种情况：
1：一串连续的数字，相邻两个数字相差1
2:2串连续的数字，每串数字相邻两个数字相差1，第一串最后一个与第二串第一个相差1，

方法一：首先，计算1到k的和与n的大小关系，看能否分成；若能够成功，则将其减去。表明已经成功分出一个从1到k的序列，然后将剩下的数分出k份，给这k个数加上，若还有，则从后开始给数加1，直到加完。

代码如下：

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <sstream>
#include <set>
#include <algorithm>
using namespace std;
typedef long long LL;

static int mod = 1000000007;
LL v[10010];

int main()
{
    int T;
    scanf ( "%d", &T );
    while( T-- )
    {
        LL n, k;
        scanf ( "%lld %lld", &n, &k );
        LL sum = k*(k+1)/2;
        LL ans = 1;
        if( sum > n )
        {
            printf("-1\n");
        }
        else
        {
            n -= sum;
            int p = n/k;
            int s = n%k;
            int i;
            for( i = 1; i <= k-s; i ++ )
                ans = (ans*(i+p))%mod;
            for( ; i <= k; i ++ )
                ans = (ans*(i+p+1))%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

方法二：既然知道了序列的排序规律以及序列的长度，那么就二分序列的起始位置或结束位置，若有剩余，按照前一个方法一样从最后一个位置依次加一。

代码如下：

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <sstream>
#include <set>
#include <algorithm>
using namespace std;
typedef long long LL;

static int mod = 1000000007;
LL v[10000010];

int main()
{
    int T;
    scanf ( "%d", &T );
    while( T-- )
    {
        LL n, k;
        scanf ( "%lld %lld", &n, &k );
        LL sum = k*(k+1)/2;
        LL ans = 1;
        if( sum > n )
        {
            printf("-1\n");
        }
        else
        {
            LL l = 1, r = n, now = 1;
            while( l <= r )
            {
                int mid = (l+r)/2;
                if(( mid+mid+k-1 )*k/2 <= n )
                {
                    l = mid+1;
                    now = mid;
                }
                else r = mid-1;
            }
            int s = (n-(now+now+k-1)*k/2);
            int i;
            for( i = 1; i <= k-s; i ++ )
                ans = (ans*(i+now-1))%mod;
            for( ; i <= k; i ++ )
                ans = (ans*(i+now))%mod;
            printf( "%lld\n", ans );
        }
    }
    return 0;
}