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

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

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

题目描述

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

思路

先看数据范围 而 。
发现 比 大很多，且如果要选择一个 那么最终的答案一定 。
所以考虑先预处理出所有 的最大公约数，再枚举所有可能的 ，通过最终答案来选择将一些 替换为 。
具体地：
对于 直接选 ；对于 就只能选 。

如何进行维护和优化：

  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
93
94
95
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<queue>
#include<vector>
#include<cmath>
#include<bitset>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
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+1;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
	read(t);read(args...);
}
template <typename T>
inline T Min(T x,T y){ return (x < y ? x : y); }
template <typename T>
inline T Max(T x,T y){ return (x > y ? x : y); }
template <typename T>
inline T Abs(T x){ return (x < 0 ? ~x+1 : x); }
const int N = 5e5+10,LG = 20;
int n;
ll st[N][LG],a[N],ans;
inline ll Gcd(ll x,ll y){
	if(!x || !y) return x|y;
	ll xz = __builtin_ctzll(x);
	ll yz = __builtin_ctzll(y);
	ll z = Min(xz,yz);
	y >>= yz;
	while(x){
		x >>= xz;
		ll diff = x-y;
		xz = __builtin_ctzll(diff);
		y = Min(x,y);
		x = Abs(diff);
	}
	return y << z;
}
inline ll query(int l,int r){
	int k = __lg(r-l+1);
	return Gcd(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
	// freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);

	read(n);
	for(int i=1;i<=n;++i){
		int x; ll y; read(x,y);
		a[x] = Gcd(a[x],y); // a一样的合并
		ans = Gcd(ans,y); // 全选b
	}
	for(int i=1;i<=N-10;++i) st[i][0] = a[i];
	for(int k=1;k<=__lg(N-10);++k){
		for(int l=1;l+(1<<k)<=N-10+1;++l){
			st[l][k] = Gcd(st[l][k-1],st[l+(1<<k-1)][k-1]);
		}
	}
	if(ans>N-10){
		printf("%lld",ans);
		return 0;
	}
	for(int i=N-10;i>ans;--i){ // 枚举答案
		ll tmp = 0;
		for(int j=1;i*j<=N-10 && !(tmp%i);++j) tmp = Gcd(tmp,query(i*(j-1)+1,i*j-1));
		if((N-10)%i) tmp = Gcd(tmp,query((N-10)-(N-10)%i+1,(N-10)));
		if(!(tmp%i)){
			ans = i;
			break;
		}
	}
	printf("%lld",ans);

	// fclose(stdin);
	// fclose(stdout);
	return 0;
}