自动搬运

查看原文

来自洛谷，原作者为

	Yxa_Sheep 打表过样例，暴力出奇迹，搜索真牛逼，骗分进省一||深搜 MLE，广搜 TLE，打表 RE，退火又 CE||删掉 display 看主页||被封取关（解封后私信）||六年级蒟蒻 ，代词请用“他”||当前状态：<离线>

搬运于2025-08-24 21:18:32，当前版本为作者最后更新于2025-06-26 15:05:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

题意

$\mu (n)=\begin{cases} 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}$ $x>1$，$p_i$ 为质数且互不相等

思路

$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)$ 就可以啦。

代码

#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;
}

题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门