自动搬运

查看原文

来自洛谷，原作者为

	紫钦 永远没有新的开始，因为我们从未停止。

搬运于2025-08-24 21:58:56，当前版本为作者最后更新于2019-07-31 19:21:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目链接：P4318 完全平方数 。

题目大意：$T$ 组数据，每组数据给出一个正整数 $K$ ，求第 $K$ 个不含大于 $1$ 的完全平方数因子的正整数。

数据规模：$T\leqslant50,1\leqslant K\leqslant10^9$ 。

解法一：杜教筛+二分

这个平方因子的问题很容易让我们想到莫比乌斯函数的性质。所以，若设答案为 $ans$ ，则有：$\sum\limits_{i=1}^{ans}[\mu(i)\neq0]=K$ 且 $\mu(ans)\neq0$ ，

考虑到 $\mu(n)$ 函数只有 $+1,0$ 和 $-1$ 三种取值，故可以使用 $\mu^2(n)$ 函数来回避 $\mu(n)=-1$ 时不好通过求前缀和来计数的情况，于是 $\sum\limits_{i=1}^{ans}\mu^2(i)=K$ 且 $\mu^2(ans)=1$ 。

题目给定 $K$ ，求解 $ans$ ，又考虑到 $\mu^2(n)$ 的前缀和必然单调不降，所以采用二分来找到 $ans$ 。二分找到的满足 $\mu^2(i)$ 的前缀和大于等于 $K$ 的最小的 $i$ 即为答案。

不过二分的范围题目没给，所以拿来题解跑了一下。发现第 $10^9$ 个不含平方因子的数是 $1644934081$ 。为了表现出我们并没有看题解的样子，所以我们将二分的上限设定为 $1644934082$ 。当然设定为 $2K$ 也可以。

其实这个数值我们可以大概计算出来，暴力算一下可计算范围内 ${\large\frac {ans}k}$ 的值，就可以大概推断出 $K=10^9$ 时的答案不超过 $2K$ 了。

当然更加可行的做法是：写好代码后，手动增加上限，并一次又一次跑 $K=10^9$ 的数据，当某次上限设定大于 $1644934081$ 时，就得到这个 $1644934081$ 的答案了，此时我们就可以让这个数做二分上限了。

二分下限就定为 $K$ 好了，显然答案是大于等于 $K$ 的。

那么二分势必带来 $\Theta(\log_2K)$ 的复杂度，这个复杂度远远达不到题目的上限。于是题目另一部分复杂度应该存在于计算 $\mu^2(n)$ 上。

设 $f(n)=\mu^2(n),S(n)=\sum\limits_{i=1}^n\mu^2(n)$ 。

数据范围达到了 $10^9$ ，而要求前缀和的 $\mu^2(n)$ 函数显然是个积性函数，所以考虑杜教筛。

那么我们就需要一个很好求前缀和的函数 $g(n)$ ，使得 $(f\times g)(n)$ 的前缀和也好求。

这个函数可相当地不好找。。。

考虑 $g(n)=[n=k^2,k\in N_+]$ ，它的前缀和并不好求。但是这种真值表达式形式的函数，拥有其特殊性：可以通过改变枚举方式，使真值表达式恒成立，从而使该函数在枚举时变为常函数。

再来考虑 $(f\times g)(n)=\sum\limits_{d|n}g(d)f({\large\frac nd})$ ，通过观察我们发现，$g(d)f({\large\frac nd})$ 仅在 $d$ 取到 $n$ 的最大平方因子时值为 $1$ ，否则值为 $0$ 。

简要证明：若 $d$ 不为 $n$ 的最大平方因子，则 ${\large\frac nd}$ 必然含有平方因子，则 $f({\large\frac nd})=\mu^2({\large\frac nd})=0$ ；若 $d$ 为 $n$ 的最大平方因子，则 ${\large\frac nd}$ 必然不含有平方因子，则 $f({\large\frac nd})=1,g(d)=1$ ；若 $d$ 不为完全平方数，则 $g(d)=0$ 。

因为 $1$ 一定是 $n$ 的一个平方因子，所以 $n$ 的最大平方因子肯定存在。

于是 $(f\times g)(n)=1(n)=1$ ，那么 $(f\times g)(n)$ 的前缀和很好求。

使用杜教筛的套路，得：

$g(1)S(n)=\sum\limits_{i=1}^n(f\times g)(i)-\sum\limits_{i=2}^ng(i)S({\large\lfloor\frac ni\rfloor})$ ，

即：$S(n)=n-\sum\limits_{i=2}^ng(i)S({\large\lfloor\frac ni\rfloor})$ ，

然后直接改变枚举方式，枚举平方数，得：

$S(n)=n-\sum\limits_{i=2}^ng(i)S({\large\lfloor\frac ni\rfloor})=n-\sum\limits_{i=2}^{\sqrt n}S({\large\lfloor\frac n{i^2}\rfloor})$ ，

这个神一般的杜教筛操作真令人眼花缭乱。

好了，现在 $g(i)$ 前缀和直接回避了，用不着求了。

注意事项

• 时间复杂度为 $\Theta(1000000+TK^\frac23\log_2K)$ ，个人感觉这个复杂度很危险，过不去的样子。

• 注意到杜教筛后面那一项只有 $\sqrt n$ 项，整除分块优化不明显，且除法常数很大，所以别整除分块。

  这是整除分块的评测记录 。

  这是没有整除分块的 。

  所以别用整除分块。

• 注意 $\text{long\ long}$ ，二分时区间左右端点要开成 $\text{long\ long}$ ，否则相加计算 $mid$ 时爆 $\text{int}$ 。其他地方不用开。我开了很多没必要的 $\text{long\ long}$ 然后 $TLE$ 了，见 $TLE$ 记录 。

$AC$ 代码

#include<cstdio>
#include<cstdlib>
#include<unordered_map>
using namespace std;
namespace Qza {
	int T,K,mu2[1000002],prime[78499]; // prime[78498]=999983;
	bool vis[1000002];
	unordered_map<int,int> map_S;
	inline void init(int x)
	{
		static int cnt=0;
		long long k;
		mu2[1]=1;
		for(register long long i=2ll;i<=x;++i) {
			if(!vis[i]) prime[++cnt]=i,mu2[i]=1;
			for(register int j=1;j<=cnt && (k=i*prime[j])<=x;++j) {
				vis[k]=true;
				if(i%prime[j]) mu2[k]=mu2[i];
				else break;
			}
			mu2[i]+=mu2[i-1];
		}
	}
	inline int S(int x) 
	{
		if(x<=1000000) return mu2[x];
		if(map_S[x]) return map_S[x];
		int res=0;
		for(register int l=2;l*l<=x;++l) {
			res+=S(x/(l*l));
		}
		return map_S[x]=x-res;
	}
	int read()
	{
		char ch=getchar(); int x=0;
		while(ch<'0' || ch>'9') ch=getchar();
		while(ch>='0'&&ch<='9') x=(x*10)+(ch^48), ch=getchar();
		return x;
	}
	void main()
	{
		T=read();
		if(!T) return ; // 杞人忧天，但是题目确实没保证 T>0。。。 
		init(1000000);
		register long long l,r;
		register int mid;
		do {
			K=read();
			l=K; r=1644934082ll; 
			while(l<r) {
				mid=(l+r)>>1;
				if(S(mid)>=K) r=mid;
				else l=mid+1;
			}
			printf("%lld\n",r);
		}while(--T);
		return ;
	}
}
int main()
{
	Qza::main();
	return 0;
}

解法二：容斥+二分

二分答案是没办法的回避的。这种求出序列第几个数是几的，经验告诉我们，平衡树 二分答案应该是不错的选择（且本题的单调性很明显）。

那么，为什么想到了容斥？

有了二分答案的步骤，我们就需要考虑如何快速求出 $[1,n]$ 内不含非 $1$ 完全平方数因子的数的个数。

我们很自然地想到，可以通过筛去完全平方数的倍数，而留下不含平方因子的数。在剩余的数上操作，要方便得多。

可惜线性筛在 $10^9$ 的数据规模下吐血而亡，所以我们不能靠筛，我们需要直接计算。

直接计算的话，我们知道，$[1,n]$ 区间内， $4$ 的倍数共有 ${\large\lfloor\frac n4\rfloor}$ 个。进一步思考发现，我们当然不会将 $16$ 的倍数再筛选去掉（再去掉就减多了）。所以我们只需要去掉所有质数的完全平方数的倍数。

嗯，这就想到容斥了。因为筛重复了。比如说 $4$ 的倍数和 $9$ 的倍数都去掉后，$36$ 的倍数就减多了，需要加回来。

由此我们想到，可以枚举 $[1,\lfloor\sqrt n\rfloor]$ 区间内的所有质数，然后容斥。这样，我们就需要先减去 $2^2,3^2,5^2,\cdots$ 的倍数的个数，再加上 $6^2,10^2,14^2,\cdots$ 的倍数的个数，再减去 $\cdots\cdots$ 。

显然工作量极大。而且枚举的顺序很难确定。

不过，我们发觉，容斥时，如果若干个相异质数（也可以为一个质数）的积大于 $\lfloor\sqrt n\rfloor$ 的话（设这个积为 $x$ ），那么 ${\large\lfloor\frac n{x^2}\rfloor}=0$ 。这就是容斥的边界。

这告诉我们，枚举的次数不超过 $\lfloor\sqrt n\rfloor$ 次。再加上枚举的数需为若干相异质数的乘积的限制条件，我们会自然想到莫比乌斯函数 $\mu(n)$ 。

莫比乌斯函数具有很好的容斥天赋。若像解法一那样，将莫比乌斯函数做个平方来计数，属实是有些屈才了。

故我们得到 $[1,n]$ 中不含非 $1$ 完全平方数因子的数的个数为 $\sum\limits_{i=1}^{\lfloor\sqrt n\rfloor}\mu(i){\large\lfloor\frac n{i^2}\rfloor}$ ，式中 $\mu(i)$ 的存在保证了 $i$ 一定为若干相异质数的积，且恰好按照质因子个数来分配系数（$+1$ 和 $-1$）。

至此，容斥思路已成型。

注意事项

• 线性筛求 $\mu(n)$ 时，考虑到 $\sqrt{1644934081}\approx40558$ ，故筛出 $40559$ 项足矣。

  万万不能由 $\sqrt{10^9}\approx31623$ 而只筛 $31624$ 项！

• 二分答案仍然要开 $\text{long\ long}$ ，除此之外，无需 $\text{long\ long}$ 。

• 同样不需要整除分块。

• 时间复杂度为 $\Theta(40559+T\sqrt K\log_2K)$ ，比杜教筛快了很多。

$AC$ 代码

评测记录 。

#include<cstdio>
#include<cstdlib>
using namespace std;
namespace Qza{
	int T,K,prime[4253],mu[40560]; // prime[4252]=40559;
	bool vis[40560];
	void init(int x)
	{
		static int cnt=0;
		int k;
		mu[1]=1;
		for(int i=2;i<=x;++i) {
			if(!vis[i]) prime[++cnt]=i, mu[i]=-1;
			for(int j=1;j<=cnt && (k=i*prime[j])<=x;++j) {
				vis[k]=true;
				if(i%prime[j]) mu[k]=-mu[i];
				else break;
			}
		}
	}
	bool judge(int x)
	{
		int ans=0;int i;
		for(i=1;i*i<=x;++i) {
			ans+=mu[i]*(x/(i*i));
		}
		return ans>=K;
	}
	int read()
	{
		char ch=getchar(); int x=0;
		while(ch<'0' || ch>'9') ch=getchar();
		while(ch>='0'&&ch<='9') x=(x*10)+(ch^48), ch=getchar();
		return x;
	}
	void main()
	{
		T=read();
		if(!T) return ;
		init(40559);
		long long l,r;
		int mid;
		do {
			K=read();
			l=K; r=1644934082ll;
			while(l<r) {
				mid=(l+r)>>1;
				if(judge(mid)) r=mid;
				else l=mid+1;
			}
			printf("%lld\n",r);
		}while(--T);
		return ;
	}
}
int main()
{
	Qza::main();
	return 0;
}