分 则 能 成 分则能成 分则能成


<mstyle mathcolor="blue"> 最 初 想 法 </mstyle> \color{blue}{最初想法} 最初想法

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

<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

最终 一定分成 K + 1 K+1 K+1 个数字, 设为 a 1 , a 2 , a 3 . . . a m a_1, a_2, a_3...a_m a1​,a2​,a3​...am​,


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

于是答案为 1 2 ∑ i = 1 m a i ∗ ( N − a i ) \frac{1}{2}\sum\limits_{i=1}^ma_i*(N-a_i) 21​i=1∑m​ai​∗(N−ai​) , 可以证明当 a i a_i ai​ 最平均时答案最大 .

m = K + 1 m = K+1 m=K+1

<mstyle mathcolor="red"> 实 现 部 分 </mstyle> \color{red}{实现部分} 实现部分

现将 N N N 分为 K + 1 K+1 K+1 份, 然后将 N % ( K + 1 ) N\%(K+1) N%(K+1) 平均分布到这 K + 1 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\n", Ans >> 1);
        return 0;
}