线性筛和质因数分解

题目大意：给定n个数，判断通过转移因数，能否形成n个相等的数，实质为判断质因数的个数。

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+10;

unordered_map<int,int> cnt;
int p[N],idx;
bool st[N];//判断是否筛过
int path[N];//存储最小质因数

void get_p()
{
    int n=1e6;
    for(int i=1;i<=n;++i)
        path[i]=i;
    for(int i=2;i<=n;++i)
    {
        if(!st[i]) p[idx++]=i;
        for(int j=0;j<idx&&p[j]*i<=n;++j)
        {
            if(!st[i*p[j]])
                {st[i*p[j]]=true;path[i*p[j]]=p[j];}
            if(i%p[j]==0)  break;//保证一个数只筛一次
        }
    }
}

void solve()
{
    cnt.clear();
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        int x;
        cin>>x;
        while(x!=1)
        {
            cnt[path[x]]++;
            x/=path[x];
        }
    }
    int tag=1;
    for(auto v:cnt)
        if(v.second%n!=0) tag=0;
    if(tag) cout<<"YES"<<"\n";
    else cout<<"NO"<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    get_p();
    while(T--)
    {
        solve();
    }
    return 0;
}

质因数

526互联

线性筛与质因数分解

线性筛和质因数分解

代码