Strongly Composite（分解质因数+思维）

题意：给定一个数组a，构造一个数组b，数组b尽可能长，且数组b里全是强合数，并且a数组所有数相乘等于b数组所有数相乘；

强合数：如果一个数的质因子的个数小于等于合数的个数，那么这个数就是强合数。

思路：分解所有质因数，两个相同的质因数，构成一个质因数，和一个合数，满足题意。

三个不相同的质因数，构成三个不同的质因数和四个不同的合数，满足题意。

因为题意是尽可能长，那么再用四个，，，n个，就不会太长。

所以就是，先枚举所有质因数的个数，优先选两个的相同的，再选三个不同的，最后答案就是两者相加。

这里有一个点：两个相同的枚举完，三个不同的枚举完，可能还剩有数（1或者2），他们可以任意加到任意一组满足条件的，从而保证数组所有数相乘等于b数组所有数相乘；剩余的数也不能对答案产生贡献，所以不用考虑，但当时可能会有点不理解，为什么不考虑；

#includeusing namespace std;
const int N = 2e5 + 10;
int a[N];
int w[N];int main()
{int t;cin>>t;while(t--){int n,k;cin>>n;for(int i=1;i<=n;i++) scanf("%d",&a[i]);unordered_map mp;for(int i=1;i<=n;i++){for(int j=2;j*j<=a[i];j++){while(a[i]%j==0) {mp[j]++;a[i]/=j;}}if(a[i]>1){mp[a[i]]++;} }int ans=0;int cnt=0;for(auto item : mp){
//       	    cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！