【BestCoder Round #76 (div.2)】DZY Loves Partition（数学分析）

FishWang

发布于 2025-08-27 08:48:00

15800

代码可运行

运行总次数：0

代码可运行

DZY Loves Partition

Accepts: 128

Submissions: 272

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

问题描述

DZY喜欢拆分数字。他想知道能否把nn拆成恰好kk个不重复的正整数之和。

思考了一会儿之后他发现这个题太简单，于是他想要最大化这kk个正整数的乘积。你能帮帮他吗？

由于答案可能很大，请模10^9+7109+7输出。

输入描述

第一行tt，表示有tt组数据。

接下来tt组数据。每组数据包含一行两个正整数n,kn,k。

(1\le t\le 50, 2\le n,k \le 10^91≤t≤50,2≤n,k≤109)

输出描述

对于每个数据，如果不存在拆分方案，输出-1−1；否则输出最大乘积模10^9 + 7109+7之后的值。

输入样例

输出样例

Hint

第一组数据没有合法拆分方案。
第二组数据方案为3=1+23=1+2，答案为1\times 2 = 21×2=2
第三组数据方案为9=2+3+49=2+3+4，答案为2\times 3 \times 4 = 242×3×4=24。注意9=3+3+39=3+3+3是不合法的拆分方案，因为其中包含了重复数字。
第四组数据方案为666666=333332+333334666666=333332+333334，答案为333332\times 333334= 111110888888333332×333334=111110888888。注意要对10^9 + 7109+7取模后输出，即110888111110888111。

当时比赛的时候好懵啊，后来才有思路。

其实想通了很简单啦。

首先要先判断一下 sum( 1 , k ) 如果大于n的话，无论如何也无法完成的，直接输出 -1 跳出即可。

然后就开始真正的解题步骤了：

答案的形成有两种可能：

①一段连续的数字

②两段连续的数字，但是第一段的最后一个和第二段的第一个相差1。

（其实不用分情况看是哪种情况，写到后面自然明白了）

首先还是要知道 sum( 1 , k ) 的，然后计算它与 n 的差值，除以 k 得到的 add 就是这 1 - k 整体要加的数（其实是得到了相加以后的数列，但是这里为了方便理解，只用1 - k ，计算的时候加上 add 就好啦。然后还有一个问题，如果得到的新数列 ( 1 + add , k + add ) 还不等于 n 时，那么这时候计算出差值（re = ( n - sum ) % k），这个 re 表示：数列的后 re 个数要再加 1 （就是让 re 个数把剩下的缺口补上，这样还是满足了最优解（就是上面说的那两种情况之一））

现在解释一下为什么不用考虑到底是哪种情况：如果是第一种情况，这个 re 的值等于 0 ，也就是说计算的时候，后 0 个数加了 0 （毫无意义 = =）。所以代码就能很简单啦。

代码如下：

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
__int64 ans,n,k,sum,add;
__int64 re;
__int64 MOD = 1e9 +7;
int main()
{
	int u;
	__int64 i;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%I64d %I64d",&n,&k);
		sum = (1 + k) * k / 2;
		if (sum > n)
		{
			printf ("-1\n");
			continue;
		}
		re = n - sum;
		add = re / k;		//需要从1增加的数 
		re %= k;
		ans = 1;
		for (i = 1 ; i <= (k-re) ; i++)
			ans = (ans * (i + add)) % MOD;
		for (int j = 1; j <= re ; j++,i++)		//这里的i++给忘了，一直WA，泪奔 
			ans = (ans * (i + add + 1)) % MOD;
		printf ("%I64d\n",ans);
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

数据