\(\text{Poblem}\)

求 \(\sum_{i=l}^r \mu(i)\)

\(1 \le l,r \le 10^{18}, r - l \le 10^5\)

\(\text{Analysis}\)

我们做过 \(r,l \le 10^{12}\) 次方的区间筛积性函数

但这是因为 \(\sqrt r\) 内的素数可以快速筛出来

又可以用这些素数处理 \(r \le 10^{12}\) 的数的积性函数

但现在 \(\sqrt r\) 已经达到 \(10^9\) 级别了

\(so...\)

我们仍然用 \(10^6\) 以内的素数处理，并将原来的数除掉这些素数

那么剩下的数 \(x\) 只有三种形式

\(3.x=p^2\)

\(2.x=p\)

\(1.x=pq\)

\(p,q \in \mathbb P，p \not = q\)

考虑第一种情况，只需要判断 \(\sqrt x\) 强转整型后再平方是否等于 \(x\)

考虑第二种情况，由于 \(x\) 可能非常大，那么就需要 \(\text{Miller Rabin}\) 来判断素数

考虑第三种情况，两个不等的素数，\(\mu\) 不变，且判完前两个情况只剩这种情况，不必再考虑

愉快解决

\(\text{Code}\)

#include<cstdio>

#include<algorithm>

#include<ctime>

#include<cmath>

using namespace std;

typedef long long LL;

const int R = 100005;

LL l, r, num[R];

int prime[600005], totp, mu[R], vis[1000005];

inline LL sqr(LL x){return x * x;}

inline void getprime()

{

	for(int i = 2; i <= 1e6; i++)

	{

		if (!vis[i]) prime[++totp] = i;

		for(int j = 1; j <= totp && i * prime[j] <= 1e6; j++)

		{

			vis[i * prime[j]] = 1;

			if (i % prime[j] == 0) break;

		}

	}

}

inline LL fmul(LL x, LL y, LL p)

{

	return (x * y - (LL)((long double)x / p * y) * p + p) % p;

}

inline LL fpow(LL x, LL y, LL p)

{

	LL res = 1;

	for(; y; y >>= 1)

	{

		if (y & 1) res = fmul(res, x, p);

		x = fmul(x, x, p);

	}

	return res;

}

inline int Miller_Rabin(LL p)

{

	srand(time(0));

	if (p <= 3) return (p == 2 || p == 3);

	if (!(p & 1)) return 0;

	LL d = p - 1, b = 0;

	while (!(d & 1)) d >>= 1, b++;

	for(int i = 0; i < 3; i++)

	{

		LL a = rand() % (p - 3) + 2, u = fpow(a, d, p), v;

		for(int j = 0; j < b; j++)

		{

			v = fmul(u, u, p);

			if ((v == 1) && (u != 1) && (u != p - 1)) return 0;

			u = v;

		}

		if (u != 1) return 0;

	}

	return 1;

}

inline LL solve()

{

	for(int i = 1; i <= r - l + 1; i++) mu[i] = 1, num[i] = l + i - 1;

	for(int i = 1; i <= totp && prime[i] <= r; i++)

		for(LL j = max(1LL, l / prime[i]); j * prime[i] <= r; j++)

		if (j * prime[i] >= l)

		{

			if (j % prime[i] == 0) mu[j * prime[i] - l + 1] = 0;

			else mu[j * prime[i] - l + 1] *= -1, num[j * prime[i] - l + 1] /= prime[i];

		}

	for(int i = 1; i <= r - l + 1; i++)

	{

		if (!mu[i] || num[i] == 1) continue;

		if (sqr(sqrt(num[i])) == num[i]) mu[i] = 0;

		else if (Miller_Rabin(num[i])) mu[i] *= -1;

	}

	LL ans = 0;

	for(int i = 1; i <= r - l + 1; i++) ans += mu[i];

	return ans;

}

int main()

{

	scanf("%lld%lld", &l, &r);

	getprime();

	printf("%lld\n", solve());

}

巴特西

LG P3653 小清新数学题

\(\text{Poblem}\)

\(\text{Analysis}\)

\(\text{Code}\)

最新文章

热门文章