【构造+贪心+分解质因数】CF868div2 C. Strongly Composite

梦里梦外; 2024-03-22 10:22 3阅读 0赞

大概思路是差不多

但是没想到两个两个配对和剩下的三个三个配对的方案

[Problem - C - Codeforces][]

题意：

![4a4543eda19243a0a344228ba3eb27f7.png][]

思路：

构造

第一个条件：考虑将a数组的数分解质因数，然后给b数组分配质因子，具体怎么分配得看后面

第二个条件：

可以转化成：

![a0e290e777ff47ca80470c8ce9fb6e63.jpeg][]

第三个条件：

要使k尽可能大，那么b数组中每个数的质因子个数就要尽可能少

三个条件转化完了，考虑结合一下条件

**构造和贪心在一起时，可以考虑用贪心策略去特殊化构造条件**

因此考虑两个相同的质因子进行配对

因为代入可得是满足条件的

三个不同的质因子配对也满足条件

因此考虑两个两个配对，多出来的三个三个配对，（因为如果两个不同的质因子配对，素因子个数为2，合因子个数为1，就不满足条件了）如果还多出来，放进任意一对都可以

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e3+10;
    
    map<int,int> mp;
    
    int n;
    int a[mxn];
    
    void solve(){
    	mp.clear();
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=1;i<=n;i++){
    		int u=a[i];
    		for(int j=2;j<=u/j;j++){
    			if(u%j==0){
    				int s=0;
    				while(u%j==0){
    					u/=j;
    					s++;
    				}
    				mp[j]+=s;
    			}
    		}
    		if(u>1) mp[u]++;
    	}
    	int ans=0,res=0;
    	for(auto it:mp){
    		ans+=it.second/2;
    		res+=it.second%2;
    	}
    	cout<<ans+res/3<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1823/problem/C
[4a4543eda19243a0a344228ba3eb27f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/928677962ff84e8db0ada0407fbd265e.png
[a0e290e777ff47ca80470c8ce9fb6e63.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/f8f0b0af1a594cdd9a4a4969395cba84.png