Codeforces Round #717 (Div. 2) D.Cut 倍增优化

题意

给定数组\(a\)，每次询问

分析

容易发现要求就是这个区间任意两个数没有公因子

其实当时贪心已经想到了，但是没想到倍增 这个套路就在前几天的EDU最后一题其实有做到

感觉还是比较常见的套路？类似可见 https://ac.nowcoder.com/acm/contest/82/B

用\(go[i][j]\)表示\(i\)出发后\(2^j\)的位置 ，我们发现此题是可以转移的

其中边界即\(go[i][0]\)可以通过预处理每个数后面第一个出现存在过的因子的位置得到

代码

const int maxn = 1e5 + 5;

int isp[maxn],last[maxn],r[maxn],v[maxn],go[maxn][18];
vector<int> g[maxn]; 
int main(){
	 
	for(int i = 2;i <= 100000;i++){
		if(isp[i]) continue;
		for(int j = i;j <= 100000;j += i) {
			g[j].push_back(i);
			isp[j] = 1;
		}
	} 
	int n = rd();
	int q = rd();
	for(int i = 1;i <= n;i++)
		v[i] = rd();
	r[n + 1] = n;
	for(int i = n;i >= 1;i--){
		r[i] = r[i + 1];
		for(auto it:g[v[i]]) {
			if(last[it]) r[i] = min(r[i],last[it] - 1);
		} 
		for(auto it:g[v[i]]) {
			last[it] = i;
		}
	}
	for(int i = 0;i <= 17;i++)
		go[n + 1][i] = n + 1;
	for(int i = n;i >= 1;i--){
		go[i][0] = r[i] + 1;
		for(int j = 1;j <= 17;j++)	
			go[i][j] = go[go[i][j - 1]][j - 1];
	}
	while(q--){
		int l = rd();
		int r = rd();
		int ans = 0 ;
		for(int i = 17;i >= 0;i--){
			if(go[l][i] <= r) 
				ans += (1 << i),l = go[l][i];
		}
		printf("%d\n",ans + 1);
	} 
}

Codeforces Round #717 (Div. 2) D.Cut 倍增优化

原文：https://www.cnblogs.com/hznumqf/p/14691150.html