P9401

标签：P9401 return cur int i64 gcd

之前的 theme 在我的老电脑上太卡了，就先不用了。换上了高贵的 PinkRabbit CSS!

gcd 这个东西没啥最优化的好性质，就是一个 log 结构有点用。这题也用不到。先考虑枚举。

注意到 \(b_i,a_i\) 不寻常的范围，如果选了一个 \(a_i\)，那么答案 \(\le 5\times 10^5\)。

特判全为 \(b_i\)。

枚举答案 \(x\)，考虑怎么选择，显然如果 \(x\) 是答案，那么不满足 \(x|a_i\) 的 \(i\) 都要满足 \(x|b_i\)。

把 \(a_i\) 扔到桶上，对于 \(x\) 有 \(\mathcal O(V/x)\) 段不满足的 \(a_i\)，那么写一个区间 gcd 即可。时间复杂度 \(\mathcal O(V\log^2 V)\)。

// Problem: P9401 [POI2020-2021R3] Kolekcjoner Bajtemonów 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9401
// Memory Limit: 256 MB
// Time Limit: 600 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using i64 = long long;

const int maxn = 1e6 + 5;
const int V = 5e5 + 5;

i64 gcd(i64 x, i64 y) {
	if(!x||!y)
		return x | y;
	if(x == 1||y == 1)
		return 1;
	int az = __builtin_ctzll(x), bz = __builtin_ctzll(y);
	int z = std::min(az, bz);
	y >>= bz;
	while(x) {
		x >>= az;
		i64 dif = x - y;
		az = __builtin_ctzll(dif);
		y = std::min(x, y);
		x = abs(dif);
	}
	return y << z;
}

int n, lg[V], mx;
i64 f[20][V];

i64 GCD(int l, int r) {
	if(r > mx)
		r = mx;
	int k = lg[r - l + 1];
	return gcd(f[k][l], f[k][r - (1 << k) + 1]);
}

int main() {
	scanf("%d", &n);
	i64 ans1 = 0;
	for(int i = 1;i <= n;++ i) {
		int a;
		i64 b;
		scanf("%d %lld", &a, &b);
		mx = std::max(mx, a);
		f[0][a] = gcd(f[0][a], b);
		ans1 = gcd(ans1, b);
	}
	for(int i = 2;i <= mx;++ i)
		lg[i] = lg[i >> 1] + 1;
	for(int k = 1;k <= lg[mx];++ k)
		for(int i = 1;i + (1 << k) - 1 <= mx;++ i)
			f[k][i] = gcd(f[k - 1][i], f[k - 1][i + (1 << k - 1)]);
	i64 ans2 = 0;
	for(int i = mx;i > ans1;-- i) {
		i64 cur = 0;
		for(int j = 0;j * i < mx&&!(cur % i);++ j)
			cur = gcd(cur, GCD(i * j + 1, i * (j + 1) - 1));
		if(!(cur % i)) {
			ans2 = i;
			break ;
		}
	}
	printf("%lld\n", std::max(ans1, ans2));
	return 0;
}

标签：P9401,return,cur,int,i64,gcd
From： https://www.cnblogs.com/663B/p/17500967.html