D. Divide and Equalize--Codeforces Round 903 (Div. 3)

D. Divide and Equalize

题意：让一组数中的一个数除以一个因子，一个数除以一个因子，假如经过若干次操作后能够使数组所有数相等，那么输出YES，否则输出NO。

分析：乘除因子，那么实际上就是因子的转移，一个数乘上这个因子，另一个数除以这个因子，总的因子数不变。
要让所有数相等，那么就要让所有因子能够整除n，这样能够使所有因子能够平均分配给每一个数。
使用map记录所有因子个数，遍历map验证整除即可。

#include
#include
using namespace std;
int main()
{
    int T;cin>>T;
    while(T--){
        int n;
        cin>>n;
        map<int,int>q;
        for(int i=1;i<=n;i++)
        {
            int t;cin>>t;
            for(int j=2;j<=t/j;j++)
            {
                while(t%j==0){
                    q[j]++;
                    t/=j;
                }
            }
            q[t]++;
        }
        int f=0;
        for(auto x:q){
            if(x.first<=1) continue;
            if(x.second%n!=0) {f=1;break;}
        }
        if(f==1) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31