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

· · 题解

Analysis

首先我们看这题显然跟质数有关，分析过程，发现 μ 的值跟质因数紧密相关。

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

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

这里附上代码：

#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

可以结合下面代码看。

  1. 粘贴我们的线性筛代码，在此基础上作改进。

  2. 首先如果是质数，直接赋值就可以。

  3. 接下来看第二层循环部分：如果包含了该质因子，那么此时 i*Prime[j] 中必有质数 Prime[j] 的平方，赋值。并注意与线性筛同理，要跳出循环。

  4. 若不包含，那么简单分析：当前的数必定在前几步或者这一步计算过，所以当前有一个 Miu[i] 的值。对于新数 i*Prime[j] 来说，相当于当前的数乘一个新的质因子。因此它的质因数幂分解式必然多了一个质因子，相比这个数，需要多乘负一。

  5. 循环结束后，计算 μ 的和。

Code

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

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