2020-10-18 08:38 已编辑杭州电子科技大学算法工程师

关注

完全平方数

https://ac.nowcoder.com/acm/problem/212437

完全平方数

题目大意

就是请你求第 $n$ 无平方因字数

分析

有感觉的同学会发现，这个似乎和 $\mu$ 有关

此话怎讲？

先考虑 $\mu$ 的定义

$\mu(x)= \begin{cases} 1\quad\qquad\text{x = 1}\\ 0\quad\qquad\text{x为某个不为1的完全平方数的倍数}\\ (-1)^k\quad\text{x为无平方因子数}\land x=p_1p_2\cdots p_k \end{cases}$

那么显然可以得到，无平方因子数的个数可以有如下表示

$count=\sum_{i=1}^n\mu^2(i)$

即所有无平方因字数的贡献都为 $1$ ，而其他数没有贡献

那么从这里开始就可以有两种做法了

容斥

就是说，要从简单的入手

用 $n$ 去减掉带有平方因子数的个数

那么就可以来枚举一下每个完全平方数对答案的贡献

那么，现在有 $p_1,p_2\cdots p_k$ 这些素数

$p_i^2$ 的贡献就有 $\left\lfloor\frac n{p_i^2}\right\rfloor$

但是例如 $p_1^2p_2^2$ 这个数它其实是被计算了两次的

多枚举几个数以后，会发现由偶数个素数构成的数会被重复计算，那么重复的部分是需要减去的

如图，红绿蓝三个交集再三个大圆中被重复计算了，中间那个像勒洛三角形的部分再减去原交集的时候同时也被剪掉了，所以又要加上它的贡献

那么回到这道题，就是说，一个数由 $k$ 个因子构成，那么他的贡献可以表示为(k & 1) ? -1 : 1

那么这不就变回了莫比乌斯函数了吗？

所以可以得到：

$ans=n-\sum_{i=2}^\sqrt n\mu(i)\left\lfloor\frac n{i^2}\right\rfloor$

就可以直接写了

用二分查找这个应该就不用说了吧

Code(100)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 5e4;
int T, A, B;
int P[Maxn + 10], Cnt;
int mu[Maxn + 10];
bool Vis[Maxn + 10];

inline void Init()
{
    mu[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Vis[i]) P[++Cnt] = i, mu[i] = -1;
        for (int j = 1; j <= Cnt && i * P[j] <= Maxn; ++j)
        {
            Vis[i * P[j]] = 1;
            if (i % P[j]) mu[i * P[j]] = -mu[i];
            else break;
        }
    }
}

bool Check(int x)
{
    int ans(x);
    for (ll i = 2, r; i * i <= x; ++i)
        ans += mu[i] * (x / i / i);
    return ans >= A;
}

inline void Find(int X)
{
    ll l(X), r(X << 1), ans(0);
    while (l <= r)
    {
        ll Mid((l + r) >> 1);
        if (Check(Mid)) ans = Mid, r = Mid - 1;
        else l = Mid + 1;
    }
    printf ("%lld\n", ans);
}

int main()
{
    Init();
    scanf ("%d", &T);
    while (T--)
    {
        scanf ("%d", &A);
        Find(A);
    }
}

这个时间复杂度是 $O(5e4+T\log n)$

理论上乱写都是可以过的

但是还是可以在稍稍优化一下

那么就要考虑对这个求和进行类整数分块

可以证明 $\left\lfloor\frac n{i^2}\right\rfloor$ 在 $i\in[1,\sqrt n]$ 的取值是连续的

那么加上这样一个分块，这道题就可以过了

Code(100)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 5e4;
int T, A, B;
int P[Maxn + 10], Cnt;
int mu[Maxn + 10];
bool Vis[Maxn + 10];

inline void Init()
{
    mu[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Vis[i]) P[++Cnt] = i, mu[i] = -1;
        for (int j = 1; j <= Cnt && i * P[j] <= Maxn; ++j)
        {
            Vis[i * P[j]] = 1;
            if (i % P[j]) mu[i * P[j]] = -mu[i];
            else break;
        }
    }
    for (int i = 1; i <= Maxn; ++i) mu[i] += mu[i - 1];
}

bool Check(int x)
{
    ll ans(x);
    for (int l = 2, r; l * l <= x; l = r + 1) {
        r = min(sqrt(x / (x / l / l)), sqrt(x));
        ans += (mu[r] - mu[l - 1]) * (x / l / l);
    }
    return ans >= A;
}

inline void Find(int X)
{
    ll l(X), r(X << 1), ans(0);
    while (l <= r)
    {
        ll Mid((l + r) >> 1);
        if (Check(Mid)) ans = Mid, r = Mid - 1;
        else l = Mid + 1;
    }
    printf ("%lld\n", ans);
}

int main()
{
    Init();
    scanf ("%d", &T);
    while (T--)
    {
        scanf ("%d", &A);
        Find(A);
    }
}

杜教筛

其实我们发现 $\mu^2(i)$ 也是一个不完全积性函数

那么就是可以考虑使用杜教筛的

杜教筛就不细说了，需要了解杜教筛的可以看我的这篇博客

考虑构造函数 $g(x)$

使得 $\mu^2*g$ 能够方便的表示

能够方便表示的函数可以想到有： $\epsilon,1,id$

那么显然 $\epsilon,id$ 是不好的得到的

那就考虑 $\mu^2*g=1$ 的 $g$ 的构造（其实可以直接 $\text{Min_25筛}$ ，不需要怎么构造别的函数）

那么就是说要让：

$\sum_{d|n}\mu^2(d)g(\frac nd)=1$

考虑 $\mu^2(d)$ 有贡献时，当且仅到 $d$ 为无平方因子数，此时要让 $g(\frac nd)$ 也有贡献，整体贡献才可能为 $1$

那么感觉一下， $g(\frac nd)$ 大概是一个与完全平方数有关的函数

那么定义 $g(x)=[x==\left\lfloor\sqrt x\right\rfloor^2]$ ，即 $x$ 是否是完全平方数

那么对于 $\mu^2*g=1$ 就是成立的了，简单证明一下：

要让 $\mu^2(d)g(\frac nd)=1$ 当且仅当 $d$ 为无平方因字数且 $\frac nd$ 为完全平方数时才有贡献

那么分两种情况考虑：

$d$ 为无平方因子数：那么显然当 $\frac nd$ 不为 $1$ 时 $g(\frac nd)$ 的函数值都为 $0$ ，那么只有 $d=n$ 时， $f(n)g(1)=1$

$d$ 不为无平方因子数：就是只有当 $\frac nd$ 为 $n$ 的最大平方因子时， $d$ 才是无平方因子数， $\frac nd$ 也是完全平方数，此时才有 $1$ 的贡献

所以证明了这个构造是没有问题的

接下来，就是杜教筛的套路：

$\begin{align*} g(1)S(n)&=\sum_{i=1}^n(\mu^2*g)(i)-\sum_{i=2}^ng(i)S(\left\lfloor\frac ni\right\rfloor)\\ g(1)S(n)&=n-\sum_{i=2}^ng(i)S(\left\lfloor\frac ni\right\rfloor)\\ \end{align*}$

考虑到 $g$ 函数的性质，会发现只有当 $i$ 为完全平方数时，才有贡献

那么这个又可以写成：

$S(n)=n-\sum_{i=2}^\sqrt n S(\left\lfloor\frac n{i^2}\right\rfloor)$

int MMu(int x)
{
    if (x <= Maxn) return mu[x];
    if (Mu[x]) return Mu[x];
    int Ans(0);
    for (int l(2); 1ll * l * l <= x; ++l) Ans += MMu(x / (l * l));
    return Mu[x] = x - Ans;
}

就是一个样子的，最后套上二分，这道题就愉快的结束了

Code(100)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
unordered_map <int, int> Mu;
const int Maxn = 1e6;
int T, A, B;
int P[Maxn + 10], Cnt;
int mu[Maxn + 10];
bool Vis[Maxn + 10];

inline void Init()
{
    mu[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Vis[i]) P[++Cnt] = i, mu[i] = 1;
        for (int j = 1; j <= Cnt && 1ll * i * P[j] <= Maxn; ++j)
        {
            Vis[i * P[j]] = 1;
            if (i % P[j]) mu[i * P[j]] = mu[i];
            else break;
        }
        mu[i] += mu[i - 1];
    }
}

int MMu(int x)
{
    if (x <= Maxn) return mu[x];
    if (Mu[x]) return Mu[x];
    int Ans(0);
    for (int l(2); 1ll * l * l <= x; ++l) Ans += MMu(x / (l * l));
    return Mu[x] = x - Ans;
}

inline void Find(int X)
{
    ll l(X), r(X << 1);
    while (l < r)
    {
        ll Mid((l + r) >> 1);
        if (MMu(Mid) >= X) r = Mid;
        else l = Mid + 1;
    }
    printf ("%lld\n", r);
}

int main()
{
    Init();
    scanf ("%d", &T);
    while (T--)
    {
        scanf ("%d", &A);
        Find(A);
    }
}

有时间的话，再用 $\text{Min_25}$ 筛写一次吧