DZY Loves Partition

时间：2023-03-08 22:11:19
问题描述
DZY喜欢拆分数字。他想知道能否把nn拆成恰好kk个不重复的正整数之和。

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

由于答案可能很大，请模109710​9​​+7输出。
输入描述
第一行tt，表示有tt组数据。

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

(1t502nk1091≤t≤50,2≤n,k≤10​9​​)
输出描述
对于每个数据，如果不存在拆分方案，输出1−1；否则输出最大乘积模109710​9​​+7之后的值。
输入样例
4

3 4

3 2

9 3

666666 2
输出样例
-1

2

24

110888111
Hint
第一组数据没有合法拆分方案。

第二组数据方案为3123=1+2，答案为1221×2=2

第三组数据方案为92349=2+3+4，答案为234242×3×4=24。注意93339=3+3+3是不合法的拆分方案，因为其中包含了重复数字。

第四组数据方案为666666333332333334666666=333332+333334，答案为333332333334111110888888333332×333334=111110888888。注意要对109710​9​​+7取模后输出，即

110888111



记sumakaa1ak1sum(a,k)=a+(a+1)+⋯+(a+k−1)。

首先，有解的充要条件是sum1knsum(1,k)≤n（如果没取到等号的话把最后一个kk扩大就能得到合法解）。

然后观察最优解的性质，它一定是一段连续数字，或者两段连续数字中间只间隔1个数。这是因为1ab21≤a<=b−2时有aba1b1ab<(a+1)(b−1)，如果没有满足上述条件的话，我们总可以把最左边那段的最右一个数字作为aa，最右边那段的最左一个数字作为bb，调整使得乘积更大。

可以发现这个条件能够唯一确定nn的划分，只要用除法算出唯一的aa使得sumaknsuma1ksum(a,k)≤n<sum(a+1,k)就可以得到首项了。

时间复杂度OnO(√​n​​​)，这是暴力把每项乘起来的复杂度。



110888111

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;

typedef long long LL;

int a[100005];

int main()

{

    int T;

    scanf("%d", &T);

    while (T--)

    {

        int n, k;

        scanf("%d %d", &n, &k);

        LL tmp = (LL)k * (k + 1) / 2;

        if (tmp > n)

        {

            puts("-1");

            continue;

        }

        for (int i = 1; i <= k; i++) a[i] = i;

        n -= tmp;

        for (int i = 1; i <= k; i++) a[i] += n / k;

        n -= n / k * k;

        for (int i = k; i >= 1 && n > 0; i--, n--) a[i]++;

        LL ans = 1;

        for (int i = 1; i <= k; i++)

        {

            ans *= a[i];

            ans %= 1000000007;

        }

        printf("%lld\n", ans);

    }

    return 0;

}

相关文章