【HDU5646 BestCoder Round 76 (div1)A】【贪心】DZY Loves Partition n个数拆分k个最大乘积

本文主要是介绍【HDU5646 BestCoder Round 76 (div1)A】【贪心】DZY Loves Partition n个数拆分k个最大乘积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DZY喜欢拆分数字。他想知道能否把$n$拆成恰好$k$个不重复的正整数之和。思考了一会儿之后他发现这个题太简单，于是他想要最大化这$k$个正整数的乘积。你能帮帮他吗？由于答案可能很大，请模10^9+710​9​​+7输出。

第一行$t$，表示有$t$组数据。接下来$t$组数据。每组数据包含一行两个正整数$n,k$。(1\le t\le 50, 2\le n,k \le 10^91≤t≤50,2≤n,k≤10​9​​)

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

4
3 4
3 2
9 3
666666 2

-1
2
24
110888111

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

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
LL n, k;
LL solve()
{LL minv = (1 + k)*k / 2;if (minv > n)return -1;LL more = (n - minv) / k;LL rst = (n - minv) % k;LL ret = 1;LL x = k - rst;for (LL i = 1; i <= x; ++i){ret = ret*(i + more) % Z;}for (LL i = x + 1; i <= k; ++i){ret = ret*(i + more + 1) % Z;}return ret;
}
int main()
{scanf("%d", &casenum);for (casei = 1; casei <= casenum; ++casei){scanf("%lld%lld", &n, &k);printf("%lld\n", solve());	}return 0;
}
/*
【题意】
把n（1e9）拆分成k（1e9）个不重复正整数之和。
使得乘积尽可能大。【类型】
贪心【分析】
其实最多拆成1e5个数。
如何使得乘积最大？
首先我们拆成最小的k个数，即(1+k)*k/2，
然后如果可以均匀提升肯定均匀提升，
然后多出来的数字我们提升较大的数。就AC啦>_<~【时间复杂度&&优化】
O(sqrt(n))*/

这篇关于【HDU5646 BestCoder Round 76 (div1)A】【贪心】DZY Loves Partition n个数拆分k个最大乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！