完全平方数

Posted on Edited on In Word count in article: 1.7k Reading time ≈ 6 mins.
真的是一道好题

完全平方数

题目大意

就是请你求第\(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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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\)的构造（其实可以直接\(\rm{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) \]

1
2
3
4
5
6
7
8
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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);
    }
}

有时间的话，再用 \(\rm{Min_{25}}\) 筛写一次吧

注意：不用开\(\text{long long}\)的地方就别开\(\text{long long}\)，不明白为什么有的\(OJ\)连这个都要卡