昨晚 CF G 题解

复仇者_帅童

2025-09-14 01:34:36

发布于：广东

1阅读

0回复

0点赞

Div.4 爆切爽！！！

题意解析：

对于长度为 $n$ 的数组 $A$ ，定义 $f(A)$ 为最后一个满足 $0\le k\lt n$ 且 $\gcd_{i=1}^k A_i\gt \gcd_{i=1}^{k+1} A_i$ 的 $k$ 。

定义 $g(A)$ 为重新排列数组 $A$ 后 $f(A)$ 的最大值。

给定一个长度为 $n$ 的数组 $A$ ，请你分别求出 $g([A_1]),g([A_1,A_2]),g([A_1,A_2,A_3]),...,g([A_1,A_2,...,A_n])$ 的值。

注意到 $f$ 函数的结果 $k$ 一定满足 $\gcd_{i=1}^{k+1} A_i=\gcd\{A\}$ ，则题目中的 $g$ 函数可以转换如下：

$g(A)$ 表示使 $A$ 数组中存在 $k$ 个数的最大公约数大于 $A$ 数组所有数的最大公约数的 $k$ 的最大值。

显然，数组选取几个数的最大公约数，一定是整个数组的最大公约数的倍数。

那么我们可以推导出一个结论：即如果选取的数的最大公约数大于整个数组的最大公约数，那么一定存在一个质数 $x$ ，使选取的数的最大公约数除以整个数组的最大公约数为 $x$ 的倍数。

考虑对每个数分解质因子。显然，每个数最多有一个大于 $\sqrt n$ 的质因子，我们可以将这个质因子提出来单独处理，记录下剩下的质因子。

对于大于 $\sqrt n$ 的质因子，我们可以通过 map 判断有多少个数有它，再选取其中不是 $\gcd$ 的质因子的最多的那个。
对于剩下的，我们可以将 $x$ 从 $2$ 枚举到 $\sqrt n$ ，判断有多少个 $A_i$ 能整除 $x\times \gcd\{A\}$ ，取最值。

最终取两者最值就是答案了。

#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>
#include <map>
using namespace std;
int a[200005], b[200005];
int fac[200005][95];
vector <int> p;
bitset <508> vis;
void solve2(int n){
	int cur = a[1];
	for(int i = 2; i <= n; i++) cur = __gcd(cur, a[i]);
	int ans = 0;
	map <int, int> mp;
	for(int i = 1; i <= n; i++){
		if(b[i] > 1 && b[i] % cur != 0){
			mp[b[i]]++; 
		}
	}
	if(mp.size() > 1){
		for(auto it:mp) ans = max(ans, it.second);
	}
	for(int i = 0; i < 95; i++){
		int tmp = 0;
		for(int j = 1; j <= n; j++){
			if(a[j] % (p[i] * cur) == 0) tmp++;
		}
		ans = max(ans, tmp);
	}
	cout << ans << ' ';
}
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 95; j++){
			int val = p[j];
			if(b[i] % val == 0){
				while(b[i] % val == 0){
					b[i] /= val;
					fac[i][j]++;
				}
			}
		}
	}
	int cur = a[1], ans = 0;
	for(int i = 1; i <= n; i++){
		solve2(i);
	}
	cout << '\n';
	for(int i = 1; i <= n; i++){
		a[i] = 0;
		b[i] = 0;
		for(int j = 0; j < 95; j++){
			fac[i][j] = 0;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	vis.set(0), vis.set(1);
	for(int i = 2; i * i <= 500; i++){
		if(vis[i]) continue;
		for(int j = i * 2; j <= 500; j += i){
			vis.set(j);
		}
	}
	for(int i = 2; i <= 500; i++){
		if(!vis[i]) p.push_back(i);
	}
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度： $O(\sum n^2(\log n+\frac{\sqrt n}{\log n}))$ 。

显然不能通过，需要优化。

优化

考虑递推处理。

对于大于 $\sqrt n$ 的部分，我们注意到 $\gcd$ 一定只能包含一个这个因子，所以我们可以记录下前两个最多的数，如果 $\gcd$ 为最多的数的倍数，则答案为第二多的数的个数。

对于小于 $\sqrt n$ 的部分，我们可以维护每个质数 $x$ ，有多少个 $j$ 满足 $\frac{A_j}{\gcd_{k=1}^{i} A_k}$ 是 $x$ 的倍数。

对于新增元素 $A_i$ ：

如果增加后 $\gcd$ 不变，则直接计算 $A_i$ 的贡献即可。
如果增加后 $\gcd$ 改变，则先计算 $\gcd$ 变成了原先的多少分之一，然后分解质因数，对每个质因子都加上 $i-1$ （因为前面的元素都有这个质因子），最后再按上面的操作即可。

最后取最大值即可。

#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>
#include <map>
using namespace std;
int a[200005], b[200005];
vector <int> p;
bitset <508> vis;
int tmp[95];
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 95; j++){
			int val = p[j];
			while(b[i] % val == 0) b[i] /= val;
		}
	}
	map <int, int> mp;
	int cur = a[1], ans = 0, mx1 = 0, mx2 = 0;
	for(int i = 1; i <= n; i++){
		int div = cur;
		cur = __gcd(cur, a[i]);
		div = div / cur;
		if(b[i] > 1){
			mp[b[i]]++;
			if(mx1 != b[i] && mx2 != b[i]){
				if(mp[mx1] < mp[b[i]]){
					mx2 = mx1;
					mx1 = b[i];
				}else if(mp[mx2] < mp[b[i]]) mx2 = b[i];
			}else{
				if(mp[mx1] < mp[mx2]) swap(mx1, mx2);
			}
		}
		if(mx1){
			if(cur % mx1 == 0) ans = max(ans, mp[mx2]);
			else ans = max(ans, mp[mx1]);
		}
		for(int j = 0; j < 95; j++){
			if(div % p[j] == 0){
				tmp[j] = i - 1;
				ans = max(ans, tmp[j]);
			}
		}
		int val = a[i] / cur;
		for(int j = 0; j < 95; j++){
			if(val % p[j] == 0){
				tmp[j]++;
				ans = max(ans, tmp[j]);
			}
		}
		cout << ans << ' ';
	}
	cout << '\n';
	
	for(int i = 1; i <= n; i++){
		a[i] = 0;
		b[i] = 0;
	}
	for(int i = 0; i < 95; i++){
		tmp[i] = 0;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	vis.set(0), vis.set(1);
	for(int i = 2; i * i <= 500; i++){
		if(vis[i]) continue;
		for(int j = i * 2; j <= 500; j += i){
			vis.set(j);
		}
	}
	for(int i = 2; i <= 500; i++){
		if(!vis[i]) p.push_back(i);
	}
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度： $O(\sum n(\log n+\frac{\sqrt n}{\log n}))$ 。

有帮助，赞一个

去预览

0/2000

全部评论 1

复仇者_帅童
d

2小时前来自广东
0

优化

全部评论 1

热门讨论