分则能成 [思维题]

$分则能成$

---

$color{blue}{最初想法}$

发现大多数情况下将数字$n$分作 $n/2-1$, $n/2$, 或 $n/2+1$ 结果最优,
然后最后一次分解直接分作 $n/2$ .

---

$color{red}{正解部分}$

最终 一定分成 $K+1$ 个数字, 设为 $a_1, a_2, a_3...a_m$,

发现 $a_i$ 之间恰好每个之间都乘了一次 累加后得到答案 .

于是答案为 $frac{1}{2}sumlimits_{i=1}^ma_i*(N-a_i)$ , 可以证明当 $a_i$ 最平均时答案最大 .

$m = K+1$

---

$color{red}{实现部分}$

现将 $N$ 分为 $K+1$ 份, 然后将 $N\%(K+1)$ 平均分布到这 $K+1$ 份中 .

#include<bits/stdc++.h>
typedef long long ll;

ll N;
ll K;

int main(){
        freopen("Split.in", "r", stdin);
        freopen("Split.out", "w", stdout);
        scanf("%lld%lld", &N, &K);
        ll Ans = (K+1-N%(K+1)) * (N/(K+1)) * (N - N/(K+1));
        Ans += (N%(K+1))*(N/(K+1)+1)*(N-N/(K+1)-1);
        printf("%lld
", Ans >> 1);
        return 0;
}

---