CF2154C2 题解

cjdstttttt

2025-10-24 20:22:31

发布于：广东

24阅读

0回复

0点赞

C2>>D 有点难绷。

题意解析：

给定一个长度为 $n$ 的数组 $A$ 和 $B$ 。你可以进行任意次操作：

选择一个正整数 $i(1\le i\le n)$ 。
花费 $B_i$ ，使 $A_i$ 的值 $+1$ 。

求最小花费，使 $A$ 存在两个数不互质。

$1\le n,A_i\le 2\times 10^5,1\le B_i\le 10^9$ 。

首先考虑已经满足条件的情况。

考虑分解质因子。如果有两个数不互质，则它们必然有至少一个质因子相同。

所以可以开个桶，枚举每一数的质因子标记在桶里，如果这个数的质因子已经出现过了，则已经满足条件了，直接输出 $0$ 。

然后我们注意到存在一种操作方法：选择两个数，把它们都变成偶数即可。

我们可以按 $B_i$ 排序，取前两个变成偶数。这样答案的上界就确定出来了： $(B_1\times (A_1\mod 2)+B_2\times (A_2\mod 2))$ 。

显然不存在对两个或以上不同的数进行操作后的花费能低于这个上界。所以我们考虑对同一个数进行操作。

注意到按 $B_i$ 排序后 $B_1\le B_2\le B_3\le...\le B_n$ ，所以对于 $i\ge 2$ ， $B_i\times 2\ge (B_1+B_2)\ge (B_1\times (A_1\mod 2)+B_2\times (A_2\mod 2))$ ，要想花费低于这个上界，最多只能操作 $1$ 次。

我们可以枚举 $2\le i\le n$ ，分别判断对 $i$ 操作一次后能否满足条件，如果能就更新答案。

那对于 $i=1$ 呢？注意到 $B_2$ 可能是 $B_1$ 的很多倍，所以枚举操作几次就行不通了。

但是我们可以枚举 $B_2$ 至 $B_n$ 的所有质因子，找到使 $A_1$ 含有这个质因子的最小操作次数。这样就能快速解决了。

这样时间复杂度是多少呢？

我们可以用埃式筛预处理出每个数的最小质因子，分解质因子时直接一直除以这个最小质因子即可。因为一个正整数 $x$ 最多含有 $\lfloor\log_2 x\rfloor$ 个质因子，所以分解质因子是 $O(n\log V)$ 的，这也是所有 $A_i$ 质因子数量之和。

显然可以 $O(n\log V)$ 判断操作一次后是否满足、求出对 $i=1$ 进行操作的花费最小值，具体可以见代码。

所以总时间复杂度是 $O(V\log \log V+\sum (n\log n+n\log V))$ ，其中 $V=2\times 10^5$ 。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define int long long
#define pii pair <int, int>
using namespace std;
int frac[200005];
bool prime[200005];
bool vis[200005];
pii a[200005];
vector <int> fracs[200005];
vector <int> allfracs;
bool cmp(pii x, pii y){
	return x.second < y.second;
}
void clear(int n){
	for(int i = 1; i <= n; i++){
		for(int j:fracs[i]){
			vis[j] = 0;
		}
		vector <int>().swap(fracs[i]);// 试试这个好不好用 
	}
	vector <int>().swap(allfracs);
}
bool check(int idx, int val){
	for(int i:fracs[idx]){
		vis[i] = 0;
	}
	vector <int> tmp;
	while(val > 1){
		tmp.push_back(frac[val]);
		val /= frac[val];
	}
	bool flag = 0;
	for(int i:tmp){
		if(vis[i]) flag = 1;
	}
	for(int i:fracs[idx]){
		vis[i] = 1;
	}
	return flag;
}
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i].first;
	for(int i = 1; i <= n; i++) cin >> a[i].second;
	sort(a + 1, a + n + 1, cmp);
	for(int i = 1; i <= n; i++){
		int cur = a[i].first;
		while(cur > 1){
			if(fracs[i].empty() || fracs[i].back() != frac[cur]) fracs[i].push_back(frac[cur]);
			cur /= frac[cur];
		}
		for(int j:fracs[i]){
			if(vis[j]){
				cout << "0\n";
				clear(n);
				return;
			}
			vis[j] = 1;
			if(i > 1) allfracs.push_back(j);
		}
	}
	int ans = (a[1].second * (a[1].first % 2)) + (a[2].second * (a[2].first % 2));
	for(int i = 2; i <= n; i++){
		if(a[i].second >= ans) break;
		if(check(i, a[i].first + 1)){
			ans = a[i].second;
			break;
		}
	}
	for(int i:allfracs){
		int tmp = a[1].first / i * i + i;
		ans = min(ans, (tmp - a[1].first) * a[1].second);
	}
	cout << ans << '\n';
	clear(n);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	frac[1] = 1;
	prime[0] = prime[1] = 1;
	for(int i = 2; i <= 200000; i++){
		if(prime[i]) continue;
		frac[i] = i;
		for(int j = i * 2; j <= 200000; j += i){
			prime[j] = 1;
			if(!frac[j]) frac[j] = i;
		}
	}
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

我爱卡常

在学校想了一会，发现还可以优化。

首先我们可以建个类似并查集的东西，快速定位到一个数不同的质因子。例如 $\text{father}[6] = 3, \text{father}[12]$ 也等于 $3$ ，因为有两个相同的质因子 $2$ 。

这样分解质因子就优化到 $O(n\omega(V))$ 了。

然后也不需要对整个数组排序，只需要让前两个 $B_i$ 最小的在前面就行了。

#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
#define pii pair <int, int>
using namespace std;
int frac[200005];
int father[200005];
bool prime[200005];
bool vis[200005];
int a[200005], b[200005];
vector <int> fracs[200005];
vector <int> allfracs;
void clear(int n){
	for(int i = 1; i <= n; i++){
		for(int j:fracs[i]){
			vis[j] = 0;
		}
		vector <int>().swap(fracs[i]);// 试试这个好不好用 
	}
	vector <int>().swap(allfracs);
}
bool check(int idx, int val){
	for(int i:fracs[idx]){
		vis[i] = 0;
	}
	bool flag = 0;
	while(val > 1){
		if(vis[frac[val]]) flag = 1;
		val = father[val];
	}
	for(int i:fracs[idx]){
		vis[i] = 1;
	}
	return flag;
}
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> b[i];
	int mx1 = 0x3f3f3f3f, mx2 = 0x3f3f3f3f, idx1 = -1, idx2 = -1;
	for(int i = 1; i <= n; i++){
		if(b[i] < mx1){
			idx2 = idx1, mx2 = mx1;
			idx1 = i, mx1 = b[i];
		}else if(b[i] < mx2){
			idx2 = i, mx2 = b[i];
		}
	}
	if(idx1 == 2 && idx2 == 1) swap(a[1], a[2]), swap(b[1], b[2]);
	else if(idx2 == 1){
		swap(a[1], a[idx1]);
		swap(b[1], b[idx1]);
		swap(a[2], a[idx1]);
		swap(b[2], b[idx1]);
	}else swap(a[1], a[idx1]), swap(a[2], a[idx2]), swap(b[1], b[idx1]), swap(b[2], b[idx2]);
	
	for(int i = 1; i <= n; i++){
		int cur = a[i];
		while(cur > 1){
			fracs[i].push_back(frac[cur]);
			cur = father[cur];
		}
		for(int j:fracs[i]){
			if(vis[j]){
				cout << "0\n";
				clear(n);
				return;
			}
			vis[j] = 1;
			if(i > 1) allfracs.push_back(j);
		}
	}
	int ans = (b[1] * (a[1] % 2)) + (b[2] * (a[2] % 2));
	for(int i = 2; i <= n; i++){
		if(b[i] >= ans) continue;
		if(check(i, a[i] + 1)){
			ans = min(ans, b[i]);
		}
	}
	for(int i:allfracs){
		int tmp = a[1] / i * i + i;
		ans = min(ans, (tmp - a[1]) * b[1]);
	}
	cout << ans << '\n';
	clear(n);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	frac[1] = 1;
	prime[0] = prime[1] = 1;
	for(int i = 2; i <= 200000; i++){
		if(prime[i]) continue;
		frac[i] = i;
		father[i] = 1;
		for(int j = i * 2; j <= 200000; j += i){
			prime[j] = 1;
			if(!frac[j]){
				frac[j] = i;
				father[j] = j / frac[j];
				if(frac[father[j]] == i){
					father[j] = father[father[j]];
				}
			}
		}
	}
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度： $O(V\log \log V+\sum n\omega(V))$ ，其中 $V=2\times 10^5$ ， $\omega(n)$ 表示 $n$ 以内不同质因子数量最大值。

有帮助，赞一个

去预览

0/2000

全部评论 4

cjdstttttt
d

20小时前来自广东
0
cjdstttttt
d

20小时前来自广东
0
复仇者_澜（不处不加团队）
d

昨天来自广东
0
cjdstttttt
d

昨天来自广东
0

我爱卡常

全部评论 4

热门讨论