昨晚CF div2 C题题解

复仇者_帅童

2025-06-02 11:40:04

发布于：广东

116阅读

0回复

0点赞

CF2112C

个人难度：黄上位 / 绿下位
标签：贪心，基础数学知识，DP

题目翻译：给定一个 $N$ 个元素的数组 $A$ 。你可以进行以下操作若干次：

选择两个正整数 $i,j(1\le i,j\le N)$ 。
将 $A_i$ 变成 $\gcd(A_i,A_j)$ ，其中 $\gcd(x,y)$ 表示 $x,y$ 的最大公约数。

求把 $A$ 数组的元素都相同的操作最小次数。 $1\le N\le 5\times 10^3$ 。

显然最后的数组 $A$ 里面的元素为 $A$ 所有元素的最大公约数。所以我们把题目变一下：
先把 $A$ 里所有元素都除以一个 $A$ 数组的所有最大公约数，然后就把问题转换成了把 $A$ 数组元素全变成 $1$ 的最小次数了。

手玩几个样例可以发现：

如果 $A$ 数组存在为 $1$ 的元素，则答案就为 $A$ 中不为 $1$ 的元素数量，因为每个不为 $1$ 的元素只需要对 $1$ 进行一次操作就行。
如果不存在，则求出把 $A$ 数组中任意一个元素变为 $1$ 的最小次数 $X$ ，然后再按上面的办法，操作次数为 $X+N-1$ 。

如何求出呢？
考虑分解质因子。显然 $\gcd(A_i,A_j)$ 的结果的质因子集合为 $A_i$ 的质因子集合与 $A_j$ 的质因子集合的交集。
所以只要 $A_j$ 没有 $A_i$ 的某个质因子， $\gcd$ 操作后 $A_i$ 的这个质因子也会消失。
我们可以求出所有 $A_i$ 有的而 $A_j$ 没有的质因子集合，然后想办法凑出个和 $A_i$ 质因子集合相同的集合（就是每个元素都得有）。
不难想到 DP。DP 代码也很好写，枚举每一个 $A_j$ 选还是不选即可。

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int a[5005];
vector <int> fac[5005];
void solve(){
	int n, gcd = -1;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(gcd == -1) gcd = a[i];
		else gcd = __gcd(gcd, a[i]);
	}
	for(int i = 1; i <= n; i++){
		a[i] = a[i] / gcd;//首先除最大公约数
	}
	for(int i = 1; i <= n; i++){
		if(a[i] == 1){//存在 1 的元素直接求
			int ans = 0;
			for(int j = 1; j <= n; j++){
				if(a[j] != 1) ans++;
			}
			cout << ans << '\n';
			return;
		}
	}
	int ans = 0x3f3f3f3f;
	for(int i = 1; i <= n; i++){//枚举每一个数
		vector <int> tmp = fac[a[i]];
		vector <int> v;
		vector <int> facs(n);
		int siz = 1 << tmp.size();
		vector <vector <int>> dp(n + 1, vector <int>(siz, 0x3f3f3f3f));
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			v.push_back(a[j]);
		}
		for(int j = 0; j < n - 1; j++){
			for(int k = 0; k < tmp.size(); k++){
				if(v[j] % tmp[k] != 0) facs[j] += (1 << k);//如果不能整除 tmp[k]，就说明没这个质因子，加入集合
			}
		}
		dp[0][0] = 0;
		for(int j = 0; j < n; j++){//dp
			for(int k = 0; k < siz; k++){
				dp[j + 1][k | facs[j]] = min(dp[j + 1][k | facs[j]], dp[j][k] + 1);//选
				dp[j + 1][k] = min(dp[j + 1][k], dp[j][k]);//不选
			}
		}
		
		ans = min(ans, dp[n][siz - 1]);//更新
	}
	cout << ans + n - 1 << '\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	for(int i = 2; i <= 5000; i++){//预处理所有的质因子
		int tmp = i;
		for(int j = 2; j * j <= i; j++){
			if(tmp % j == 0){
				while(tmp % j == 0) tmp /= j;
				fac[i].push_back(j);
			}
		}
		if(tmp != 1) fac[i].push_back(tmp);
	}
	
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

我们看看时间复杂度：
显然 $5000$ 范围内，一个数顶多有 $5$ 个质因子。所以质因子集合大小不超过 $5$ 。
所以总时间复杂度为 $O(\sum n^2\times 2^k)$ ，其中 $k=5$ 。
最大计算次数为 $8\times 10^8$ ，会超时。
思考一下怎么优化。

优化 1

我们发现总共的状态总数也不超过 $2^k$ 个，而重复的状态是无效的，只需保留一个即可。
所以我们可以用这种方法大大减小 DP 的状态数。
时间复杂度降低为 $O(\sum (n^2\times k+n\times (2^k)^2))$ 。

优化 2

注意到有 $5$ 个不同质因子的只有 $7$ 个数，有 $4$ 个的只有 $336$ 个数。
而且显然重复的 $A_i$ 对降到 $1$ 没有任何作用，所以我们去重一下，就可以把实际的 $k$ 降到 $3$ 左右了。

code：

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int a[5005];
vector <int> fac[5005];
void solve(){
	int n, gcd = -1;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(gcd == -1) gcd = a[i];
		else gcd = __gcd(gcd, a[i]);
	}
	for(int i = 1; i <= n; i++){
		a[i] = a[i] / gcd;
	}
	for(int i = 1; i <= n; i++){
		if(a[i] == 1){
			int ans = 0;
			for(int j = 1; j <= n; j++){
				if(a[j] != 1) ans++;
			}
			cout << ans << '\n';
			return;
		}
	}
	int ans = 0x3f3f3f3f;
    sort(a + 1, a + n + 1);
	int realn = unique(a + 1, a + n + 1) - a - 1;//去重 
	for(int i = 1; i <= realn; i++){
		vector <int> tmp = fac[a[i]];
		vector <int> v; 
		int siz = 1 << tmp.size();
		vector <bool> vis(siz);//开个桶记录可能的状态
		
		for(int j = 1; j <= realn; j++){
			if(i == j) continue;
			v.push_back(a[j]);
		}
		for(int j = 0; j < realn - 1; j++){
			int state = 0;
			for(int k = 0; k < tmp.size(); k++){
				if(v[j] % tmp[k] != 0) state += (1 << k);
			}
			vis[state] = 1;//记录
		}
		vector <int> facs;
		for(int i = 0; i < siz; i++){
			if(vis[i]) facs.push_back(i);//如果有，添加一个即可
		}
		vector <vector <int>> dp(facs.size() + 1, vector <int>(siz, 0x3f3f3f3f));
		dp[0][0] = 0;
		for(int j = 0; j < facs.size(); j++){
			for(int k = 0; k < siz; k++){
				dp[j + 1][k | facs[j]] = min(dp[j + 1][k | facs[j]], dp[j][k] + 1);
				dp[j + 1][k] = min(dp[j + 1][k], dp[j][k]);
			}
		}
		
		ans = min(ans, dp[facs.size()][siz - 1]);
	}
	cout << ans + n - 1 << '\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	for(int i = 2; i <= 5000; i++){
		int tmp = i;
		for(int j = 2; j * j <= i; j++){
			if(tmp % j == 0){
				while(tmp % j == 0) tmp /= j;
				fac[i].push_back(j);
			}
		}
		if(tmp != 1) fac[i].push_back(tmp);
	}
	
	int t;
	cin >> t;
	while(t--) solve();
 
	return 0;
}

测了一下，202ms。提交记录

有帮助，赞一个

去预览

0/2000

全部评论 9

小鱼
%%%

12小时前来自浙江
0
pipilong2024
%%%

1周前来自浙江
0
pipilong2024
现在才发现 ST 的码风是没有万能头的 qwq

1周前来自浙江
0
- 复仇者_帅童
  回复pipilong2024
  是这样的，因为懒得打万能头（？
  
  1周前来自广东
  0
- pipilong2024
  回复复仇者_帅童
  打万能头不会快一点吗？只有一行？
  
  1周前来自浙江
  0
pipilong2024
去重是什么？awa，我用 map，嘻嘻

1周前来自浙江
0
- 复仇者_帅童
  回复pipilong2024
  六百六十六
  
  1周前来自广东
  0
复仇者_帅童
卧槽unique前面忘加sort了

1周前来自广东
0
XRaiB
%%%

1周前来自广东
0
复仇者_帅童
要不我还是写个去重

1周前来自广东
0
BaiRX
%%%

1周前来自北京
0
- 复仇者_帅童
  回复BaiRX
  你
  
  1周前来自广东
  0
复仇者_帅童
顶

1周前来自广东
0

优化 1

优化 2

全部评论 9

热门讨论