P3583 [POI2015] KWA 题解

· · 题解

题意

设 k(n) 表示将正整数 n 拆分成若干不同的平方数之和的所有方案中，最大的底数最小可能是多少，如果不存在这样的拆分，则 k(n) = \infty。

定义一个数 x 「超重」，当且仅当存在 y > x，使得 k(y) < k(x)。

给定 n，求 k(n) 和 1 \sim n 中「超重」的数个数。

题解

设 S_n=\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}，t_n 满足 S_{t_n-1}\lt n\le S_{t_n}，则 k(n)\ge t_n。

对于第一问，当 n\le285 时，可以 O(n\sqrt n) 时间内 dp 出答案，且该范围内只有 31 个数无法被表示出；当 n>285 时，t_n\ge10。

首先 128\le x\le285 时由 dp 可知都有 k(x)\ne\infty，k(x)\le t_x+1。

假设我们已经归纳证明了 128\lt x\le n-1 时都有 k(x)\ne\infty，k(x)\le t_x+1，则 x=n 时：

若 k(S_t-n)<t_n，则容易构造方案使得 k(n)=t_n；否则 k(n)\gt t_n，且由于 n-(t_n+1)^2\gt S_{t_n-1}-(t_n+1)^2\ge S_9-10^2=185，故 k(n-(t_n+1)^2)\ne\infty。

又由于 n-(t_n+1)^2\le S_{t_n}-(t_n+1)^2\lt S_{t_n-1}，故由归纳假设知 k(n-(t_n+1)^2)\le t_{n-(t_n+1)^2}\le t_n-1，因此可以构造方案使得 k(n)=t_n+1。

因此该结论成立，可以通过递归在 O(\log n) 时间内求出答案。

对于第二问，由上述结论知当 t\gt31 且 S_{t-1}\lt x\le S_t 时，t\le k(x)\le t+1，因此该范围内所有超重的数即为 k(x)=t+1 的数。又由之前结论的推导过程可知该范围内恰有 31 个数的 k 值为 t+1，为所有的 S_t-x 满足 k(x)=\infty，因此可分成 S_t\le n 和 S_{t-1}\lt n\le S_t 两部分分别统计答案。

总时间复杂度 O(\log n)。

Code

#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f
using namespace std;
int Mx=10416;
LL n,ans=0;
int f[10422];
inline LL S(LL x)
{
    return x*(x+1)*(2*x+1)/6;
}
inline int get(LL x)
{
    int t=pow(x*3,1.0/3);
    while(S(t-1)>=x)--t;
    while(S(t)<x)++t;
    return t;
}
inline int F(LL x)
{
    if(x<=Mx)return f[x];
    int t=get(x);
    return t+(F(S(t)-x)>=t);
}
int main()
{
    scanf("%lld",&n);
    if(n<Mx)Mx=n;
    for(int i=1;i<=Mx;++i)f[i]=inf;
    for(int i=1;i*i<=Mx;++i)for(int j=Mx;j>=i*i;--j)if(f[j-i*i]<inf)f[j]=min(f[j],i);
    if(n<=Mx && f[n]==inf)putchar('-');
    else printf("%d",F(n));
    for(int i=1;i<=Mx;++i)ans+=(f[i]==inf || S(f[i]-1)>i);
    if(Mx<n)
    {
        int t=get(n);
        ans+=31LL*(t-32);
        for(int i=1;i<=128;++i)ans+=(f[i]==inf && S(t)-i<=n);
    }
    return 0&printf(" %lld",ans);
}