hdu5646(数学)

小学数学，脑补

一开始看到这题，猜了个规律想写但是我是拒绝的。

因为我无法证明。

好吧，主要还是小学数学没学好吧。

要理解这题，首先得搞懂一个重要问题。假设C=A+B,怎样选择两个正整数使得A*B最大?

学过小学数学的人都知道，A=C/2,B=C-A。为啥是这样的。我在做这题之前好像就没搞太明白。

对于A+2<=B,

(A+1)(B-1) = AB+B-A-1>AB

所以对于任意选择的两个A,B都死通过调整得到A=C/2,B=C-A

推广一下，现在是对于多个数，A1,A2,A3,...,Ak

且A1+A2+A3+...+Ak=n

使得A1*A2*A3*...*Ak最大。我们发现完全可以当成若干个C=A+B问题来解。

把大的调小，把小的调大。最后得到的一定是一段连续数字，或者两段连续数字中间只间隔1个数。

如：234567

　　234678

然后这题就是一个10几行代码的模拟了。

//

//  main.cpp

//  bc76

//

//  Created by 陈加寿 on 16/3/19.

//  Copyright © 2016年 chenhuan001. All rights reserved.

//

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <algorithm>

using namespace std;

#define MOD 1000000007

long long save[];

int main(int argc, const char * argv[]) {

    int T;

    cin>>T;

    while(T--)

    {

        long long n,k;

        cin>>n>>k;

        if(k*(k+)/>n)

        {

            printf("-1\n");

            continue;

        }

        long long x = (n - k*(k-)/)/k;

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

            save[i] = x+i-;

        long long last = (n - k*(k-)/)%k;

        for(int i=;i<last;i++)

            save[k-i]++;

        long long ans=;

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

            ans = (ans*save[i])%MOD;

        cout<<ans<<endl;

    }

    return ;

}

巴特西

hdu5646(数学)

最新文章

热门文章