题解：B4308 [蓝桥杯青少年组国赛 2024] 第三题

Analysis

首先我们看这题显然跟质数有关，分析过程，发现

μ

的值跟质因数紧密相关。

那么我们必须要了解的前置知识：【P3383】线性筛素数、判断素数等。

请先完成【P3383】，掌握线性筛的求法，可以自己手推一下过程，要好好理解它的思想、过程。

这里附上代码：

CPP

#include <iostream>
const int N = 1e8+5;
using namespace std;

int n, m;
int prime[6000005]; // 保存素数，同时避免12被2,3多次筛这样的情况
bool is_not_prime[N]; // 0和1都不是素数

// 筛选 n 以内的所有素数
void Seg(int n)
{
    is_not_prime[1]=1;
    is_not_prime[0]=1;
	for (int i = 2; i <= n; ++i)
	{
		if (!is_not_prime[i])   // 如果i是素数
		{
			prime[++prime[0]] = i;
		}
		for (int j = 1; j <= prime[0] && i * prime[j] <= n; ++j)
		{
			is_not_prime[i*prime[j]] = 1;
			// 如果i中包含了该质因子，则停止
			if (i % prime[j] == 0) break;
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	Seg(n);
	for (int i = 1, q; i <= m; i++)
	{
		cin >> q;
		cout << prime[q] << '\n';
	}
}

完成之后，注意到此题目数据范围很大，肯定不能暴力硬解，自然想到线性筛，可以在线性筛的过程中，求出

μ

函数的值。

Solution

可以结合下面代码看。

粘贴我们的线性筛代码，在此基础上作改进。
首先如果是质数，直接赋值就可以。
接下来看第二层循环部分：如果包含了该质因子，那么此时 i*Prime[j] 中必有质数 Prime[j] 的平方，赋值。并注意与线性筛同理，要跳出循环。
若不包含，那么简单分析：当前的数必定在前几步或者这一步计算过，所以当前有一个 Miu[i] 的值。对于新数 i*Prime[j] 来说，相当于当前的数乘一个新的质因子。因此它的质因数幂分解式必然多了一个质因子，相比这个数，需要多乘负一。
循环结束后，计算 $μ$ 的和。

Code

按照上面的思路，简单打出代码：

CPP

#include <bits/stdc++.h>
#define N 20000005
#define M 3000005
using namespace std;

int n, m, ans;
int Prime[M], Miu[N]; //素数，μ
bool Is_Not_Prime[N];

void CulMiu(int n)
{
	Is_Not_Prime[1] = Is_Not_Prime[0] = 1, Miu[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		if (!Is_Not_Prime[i])	// 如果i是素数
		{
			Prime[++Prime[0]] = i;
			Miu[i] = -1;	// 素数为-1
		}
		for (int j = 1; j <= Prime[0] && i * Prime[j] <= n; ++j)
		{
			Is_Not_Prime[i*Prime[j]] = 1;
			if (i % Prime[j] == 0)	// 如果i中包含了该质因子，则停止（前面已经处理过）
			{
				Miu[i * Prime[j]] = 0;	//此时i*Prime[j]中必有一个质数的平方
				break;
			}
			else	//i中没有这个质因子
			{
				//当前的i必定在前几步或者这一步计算过，所以当前有一个μ[i]的值
				//对于新数i*Prime[j]，相当于i乘一个新的质因子
				//因此它的质因数幂分解式必然多了一个质因子，相比i，需要多乘-1
				Miu[i * Prime[j]] = -Miu[i];
			}
		}
	}
}

signed main()
{
	cin >> n >> m;
	CulMiu(m);
	for (int i = n; i <= m; i++) ans += Miu[i];
	cout << ans;
}

题解：B4308 [蓝桥杯青少年组国赛 2024] 第三题

文章操作

Analysis

Solution

Code

相关推荐

评论

题解：B4308 [蓝桥杯青少年组国赛 2024] 第三题