G5008 [GESP202406 五级] 小杨的幸运数字 题解

知识点：数论、筛法、质因数计数。

解题思路

筛素数，并给每个素数的全部倍数增加1，得到各数不同质因子的个数，查询是否恰有2种。

为什么正确

每个质因子只贡献一次，累计值正是不同质因子数量，与幸运数字条件一致。

易错点

统计不同质因子种类，不累计指数；例如12的2和3共两种。

复杂度

筛界M时预处理O(M log log M)，查询O(1)，空间O(M)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int M=1000000;
    vector<int>c(M+1);
    for(int p=2;p<=M;p++)if(!c[p])for(int j=p;j<=M;j+=p)c[j]++;
    int n,x;
    cin>>n;
    while(n--) {
        cin>>x;
        cout<<(c[x]==2)<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。