[蓝桥杯青少年组省赛 2023] 质因数的个数(Maximum Prime Factor Count) 题解

思路分析

注意本题统计的是计重数的质因数总个数 $\Omega(x)$（如 $8 = 2 \times 2 \times 2$ 计为 $3$ 个，$1$ 计为 $0$ 个）。由于 $M \le 10^7$，逐个做 $O(\sqrt{x})$ 试除会超时；使用欧拉线性筛在 $O(M)$ 时间内递推：对质数 $p$ 有 $\Omega(p) = 1$，筛合数 i * p 时有 $\Omega(i \cdot p) = \Omega(i) + 1$（用 uint8_t 数组仅需 $10\text{ MB}$ 内存），最后在 $[N, M]$ 上取最大值即可。

参考代码

#include <algorithm>
#include <cstdint>
#include <iostream>
using namespace std;

const int MX = 10000005;
uint8_t omegaArr[MX];
int primes[700000];
int pCnt = 0;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if (!(cin >> N >> M)) return 0;
    for (int i = 2; i <= M; ++i)
    {
        if (omegaArr[i] == 0)
        {
            omegaArr[i] = 1;
            primes[pCnt++] = i;
        }
        for (int j = 0; j < pCnt; ++j)
        {
            long long v = 1LL * i * primes[j];
            if (v > M) break;
            omegaArr[v] = uint8_t(omegaArr[i] + 1);
            if (i % primes[j] == 0) break;
        }
    }
    int ans = 0;
    for (int i = N; i <= M; ++i)
    {
        if (omegaArr[i] > ans) ans = omegaArr[i];
    }
    cout << ans << "\n";
    return 0;
}