题解：B4308 [蓝桥杯青少年组国赛 2024] 第三题
Yxa_Sheep
·
·
题解
题目传送门
题意
1 & \text{ if } n= 1\\
0 & \text{ if } n= x^2\mid n\\
(-1)^k & \text{ if } n= \textstyle\prod_{i=1}^{k}p_i
\end{cases}
## 思路
$n$ 和 $m$ 这么大，而且还出现了质数这两个字，那必须先欧拉筛了。筛着筛着我们发现，$\mu (i)$ 中，如果 $i$ 为质数，**那么 $\mu (i)=(-1)^1$，也就是 $-1$**。每次设 $x$ 为自然数，$y$ 为质数，那么 $x\times y$ 为会被筛掉，$x\times y$ 比 $x$ 的质因数多一个（就是 $y$ 嘛），**因此 $\mu (x\times y)=-\mu(x)$**。最后从 $\mu (m)$ 加到 $\mu (n)$ 就可以啦。
## 代码
```cpp
#include <bits/stdc++.h>
#define N 20000010
using namespace std;
int m, n, ans, t, p[N], f[N];
bool isp[N];
void init()
{
memset(isp, true, sizeof(isp));
isp[0] = isp[1] = false, f[1] = 1;
for (int i = 2; i <= n; i++)
{
if (isp[i])
p[++t] = i, f[i] = -1;
for (int j = 1; j <= t && i * p[j] <= n; j++)
{
isp[i * p[j]] = false;
if (!(i % p[j]))
{
f[i * p[j]] = 0;
break;
}
else
f[i * p[j]] = -f[i];
}
}
}
int main()
{
scanf("%d%d", &m, &n);
init();
for (int i = m; i <= n; i++)
ans += f[i];
printf("%d", ans);
return 0;
}
```
题解来之不易，且看且珍惜。给个赞再走吧。
**[题目传送门](https://www.luogu.com.cn/problem/B4308)**