官方题解

T2 小午的质因子统计

题目大意

求所有数质因数分解后有多少个不同的质因子。

题解思路

可以用埃式筛先预处理出 $[1,10^6]$ 所有数的质因子有哪些，然后遍历数组用 $set$ 容器存储所有质因子，因为 $set$ 容器会自动去重，所以最后直接输出 set 容器的 size() 即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<bool>st(1000010);
vector<int>f[1000010];

void init(){
    for(int i=2;i<=1000000;i++){
        if(st[i]) continue;
        for(int j=i;j<=1000000;j+=i){
            st[j]=true;
            f[j].push_back(i);
        }
    }
}

void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];

    unordered_set<int>s;
    for(int i=1;i<=n;i++){
        for(auto x:f[a[i]]){
            s.insert(x);
        }
    }

    cout<<s.size()<<endl;
}

signed main(){
    init();
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}