DZY Loves Partition
题目连接：
http://acm.hdu.edu.cn/showproblem.php?pid=5646
Description
DZY loves partitioning numbers. He wants to know whether it is possible to partition n into the sum of exactly k distinct positive integers.
After some thinking he finds this problem is Too Simple. So he decides to maximize the product of these k numbers. Can you help him?
The answer may be large. Please output it modulo 109+7.
Input
First line contains t denoting the number of testcases.
t testcases follow. Each testcase contains two positive integers n,k in a line.
(1≤t≤50,2≤n,k≤109)
Output
For each testcase, if such partition does not exist, please output −1. Otherwise output the maximum product mudulo 109+7.
Sample Input
4
3 4
3 2
9 3
666666 2
Sample Output
-1
2
24
110888111
Hint
题意
给你一个数n，你需要把n分成k个不同的数的和，然后使得这k个数的乘积最大。
题解：
首先，肯定是都挨着答案最大，所以公差为1的等差数列最好了。
然后我们二分那个等差数列的起始点的位置就好了。
如果还有数剩下来，我们就给后面的数+1就好了。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int mod = 1e9+7;
long long n,k;
long long a[maxn];
void solve()
{
scanf("%lld%lld",&n,&k);
if(1ll*(1+k)*k/2>n)
{
puts("-1");
return;
}
int l = 1,r = n,ans = 1;
while(l<=r)
{
int mid=(l+r)/2;
if(1ll*(mid+mid+k-1)*k/2<=n)l=mid+1,ans=mid;
else r=mid-1;
}
int p = (n-1ll*(ans+ans+k-1)*k/2);
for(int i=1;i<=k;i++)a[i]=ans+(i-1);
for(int i=k;i>k-p;i--)a[i]++;
long long Ans = 1;
for(int i=1;i<=k;i++)
Ans=(Ans*a[i])%mod;
cout<<Ans<<endl;
}
int main()
{
int t;scanf("%d",&t);
while(t--)solve();
}