P9401 [POI 2020/2021 R3] Kolekcjoner Bajtemonów 2

发表于 分类于 本文字数： 2.6k 阅读时长 ≈ 3 分钟

题目描述

给定 个数对，在每个数对中选一个数，最大化所选的 个数的最大公约数。

思路

先看数据范围 而 。
发现 比 大很多，且如果要选择一个 那么最终的答案一定 。

所以考虑先预处理出所有 的最大公约数，再枚举所有可能的 ，通过最终答案来选择将一些 替换为 。
具体地：
对于 直接选 ；对于 就只能选 。

如何进行维护和优化：

  1. 考虑基于值域进行处理。令 ，此时更新答案需要求 中 个区间的 的 GCD。用 ST 表维护区间 GCD，每次暴力查询判断答案是否合法。

  2. 如果使用循环递归求 GCD 其常数十分大会被卡飞，请使用二进制求 GCD。

复杂度分析：

  1. ST 表预处理 GCD 单次查询 ；

  2. 总查询次数为调和级数 。

总复杂度 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<climits>
#include<cstdlib>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&x){
	int w=0;x=0;
	char ch = getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=1;
		ch = getchar();
	}
	while(ch>='0'&&ch<='9'){
		x = (x<<1)+(x<<3)+(ch^48);
		ch = getchar();
	}
	if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
	read(t);read(args...);
}
const ll N = 5e5;//答案最大值
inline ll Max(ll a,ll b){//据说会有玄学优化
	return (a > b ? a : b);
}
inline ll Min(ll a,ll b){
	return (a < b ? a : b);
}
inline ll Abs(ll a){
	return (a < 0 ? -a : a);
}
inline ll Gcd(ll x,ll y){//基于二进制下位运算的GCD，常数十分的小
	if(!x || !y) return x|y;
	ll xz = __builtin_ctzll(x);
	ll yz = __builtin_ctzll(y);
	ll z = Min(xz,yz),diff;
	y >>= yz;
	while(x){
		x >>= xz;
		diff = x-y;
		xz = __builtin_ctzll(diff);
		y = Min(x,y);
		x = Abs(diff);
	}
	return y << z;
}
int n,lg[N+10]={-1};
ll ans,gcdd,st[N+10][20],ai[N+10];
inline ll query(ll l,ll r){//ST表查询
	int k = lg[r-l+1];
	return Gcd(ans,Gcd(st[l][k],st[r-(1<<k)+1][k]));
}
int main(){
	read(n);
	ll y;
	for(int i=1,x;i<=n;++i){
		read(x,y);
		ai[x] = Gcd(ai[x],y);//按照值域进行维护
		gcdd = Gcd(gcdd,y);//只选b的情况
	}
	for(int i=1;i<=N;++i){
		lg[i] = lg[i>>1]+1;
		st[i][0] = ai[i];
	}
	for(int k=1;k<20;++k){
		for(int l=1;l+(1<<k)<=N+1;++l){
			st[l][k] = Gcd(st[l][k-1],st[l+(1<<k-1)][k-1]);
		}
	}
	for(ll i=N;i>gcdd;--i){//枚举所有可能的答案
		ans = 0;
		ans = query(1,i-1);
		if(N%i) ans = query(N/i*i+1,N);
		for(ll j=2;i*j<=N && !(ans%i);++j){//对值域中的 i/j 个区间求GCD
			ans = query(i*(j-1)+1,i*j-1);
		}
		if(!(ans%i)){//答案需要为全部区间的GCD的因数
			printf("%lld",i);
			return 0;
		}
	}
	printf("%lld",gcdd);//只选b的情况
	return 0;;
}