Project Euler 688

题目

Piles of Plates

We stack \(n\) plates into \(k\) non-empty piles where each pile is a different size. Define \(f(n,k)\) to be the maximum number of plates possible in the smallest pile. For example when \(n = 10\) and \(k = 3\) the piles \(2,3,5\) is the best that can be done and so \(f(10,3) = 2\). It is impossible to divide \(10\) into \(5\) non-empty differently-sized piles and hence \(f(10,5) = 0\).

Define \(F(n)\) to be the sum of \(f(n,k)\) for all possible pile sizes \(k\ge 1\). For example \(F(100) = 275\).

Further define \(S(N) = \displaystyle\sum_{n=1}^N F(n)\). You are given \(S(100) = 12656\).

Find \(S(10^{16})\) giving your answer modulo \(1\,000\,000\,007\).

解决方案

令\(N=10^{16}.\)

如果\(n\)个盘子放成\(k\)堆，那么一种贪心的方法则是先摆成\(1,2,3,\dots,k-1,k\)这\(k\)堆，接下来将剩下的\(n-\dfrac{k(k+1)}{2}\)碟子再均分到这\(k\)堆，如果剩下的碟子依然不能均分，那么全部都分给最大的那堆。因此不难写出函数\(f\)为：

\[ f(n,k)= \left \{\begin{aligned} &0 & & \text{if}\quad n<\dfrac{k(k+1)}{2} \\ &1+\left\lfloor\dfrac{n}{k}-\dfrac{k+1}{2}\right\rfloor & & \text{else} \end{aligned}\right. \]

不过，这个式子其实对解题并没有太大的帮助。

将\(S\)的定义式子进行改写：

\[S(N)=\sum_{n=1}^N\sum_{k\ge 1}f(n,k)=\sum_{1\le \frac{k(k+1)}{2}\le N}\sum_{n=\frac{k(k+1)}{2}}^{N}f(n,k)\]

本质上，是将\(n,k\)的枚举顺序改变了。

式子\(\sum_{n=\frac{k(k+1)}{2}}^{N}f(n,k)\)的值可以以\(O(1)\)的时间复杂度进行计算。因为按照此时\(n\)枚举顺序，\(f(n,k)\)将会是连续\(k\)个\(1\)，\(k\)个\(2\)，……考虑分块然后使用等差数列求和进行计算。

令\(x=N-\dfrac{k(k+1)}{2}+1\)，\(q=\left\lfloor\dfrac{x}{k}\right\rfloor,r=x\%k\)，那么分块后计算得\(\sum_{n=\frac{k(k+1)}{2}}^{N}f(n,k)=k\cdot\dfrac{q\cdot(q+1)}{2}+(q+1)\cdot r\)。

最终枚举\(k\)并将这些值相加即可。

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll Q=1e16;
ll mod=1e9+7;
ll inv2=(mod+1)>>1;
int main(){
    ll ans=0;
    for(ll k=1;;k++){
        ll w=k*(k+1)/2;
        if(w>Q) break;
        ll t=Q-w+1;
        ll q=t/k%mod,r=t%k;
        ans=(ans+k*q%mod*(q+1)%mod*inv2%mod+(q+1)*r%mod)%mod;
    }
    printf("%lld\n",ans);
}