昨晚CF div2 C题题解
2025-06-02 11:40:04
发布于：广东
152阅读
0回复
0点赞
CF2112C
个人难度：黄 上位 / 绿 下位
标签：贪心，基础数学知识，DP
题目翻译：给定一个 个元素的数组 。你可以进行以下操作若干次：
- 选择两个正整数 。
- 将 变成 ，其中 表示 的最大公约数。
求把 数组的元素都相同的操作最小次数。。
显然最后的数组 里面的元素为 所有元素的最大公约数。所以我们把题目变一下：
先把 里所有元素都除以一个 数组的所有最大公约数，然后就把问题转换成了把 数组元素全变成 的最小次数了。
手玩几个样例可以发现：
- 如果 数组存在为 的元素，则答案就为 中不为 的元素数量，因为每个不为 的元素只需要对 进行一次操作就行。
- 如果不存在，则求出把 数组中任意一个元素变为 的最小次数 ，然后再按上面的办法，操作次数为 。
如何求出呢？
考虑分解质因子。显然 的结果的质因子集合为 的质因子集合与 的质因子集合的交集。
所以只要 没有 的某个质因子， 操作后 的这个质因子也会消失。
我们可以求出所有 有的而 没有的质因子集合，然后想办法凑出个和 质因子集合相同的集合（就是每个元素都得有）。
不难想到 DP。DP 代码也很好写，枚举每一个 选还是不选即可。
#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;
}
我们看看时间复杂度：
显然 范围内，一个数顶多有 个质因子。所以质因子集合大小不超过 。
所以总时间复杂度为 ，其中 。
最大计算次数为 ，会超时。
思考一下怎么优化。
优化 1
我们发现总共的状态总数也不超过 个，而重复的状态是无效的，只需保留一个即可。
所以我们可以用这种方法大大减小 DP 的状态数。
时间复杂度降低为 。
优化 2
注意到有 个不同质因子的只有 个数，有 个的只有 个数。
而且显然重复的 对降到 没有任何作用，所以我们去重一下，就可以把实际的 降到 左右了。
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。提交记录
有帮助，赞一个