解题报告 P4318 完全平方数

紫钦 · 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) 的前缀和很好求。

使用杜教筛的套路，得：