自动搬运

查看原文

来自洛谷，原作者为

	18Michael 只是也总祈望光线彼端未歇的繁星。

搬运于2025-08-24 21:50:25，当前版本为作者最后更新于2022-04-18 10:41:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

设 $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);
}