本文主要是介绍Codecraft-18 and Codeforces Round #458 D. Bash and a Tough Math Puzzle（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Bash likes playing with arrays. He has an array a1, a2, ... an of n integers. He likes to guess the greatest common divisor (gcd) of different segments of the array. Of course, sometimes the guess is not correct. However, Bash will be satisfied if his guess is almost correct.
Suppose he guesses that the gcd of the elements in the range [l, r] of a is x. He considers the guess to be almost correct if he can change at most one element in the segment such that the gcd of the segment is x after making the change. Note that when he guesses, he doesn't actually change the array — he just wonders if the gcd of the segment can be made x. Apart from this, he also sometimes makes changes to the array itself.
Since he can't figure it out himself, Bash wants you to tell him which of his guesses are almost correct. Formally, you have to process qqueries of one of the following forms:
- 1 l r x — Bash guesses that the gcd of the range [l, r] is x. Report if this guess is almost correct.
- 2 i y — Bash sets ai to y.
Note: The array is 1-indexed.
The first line contains an integer n (1 ≤ n ≤ 5·105) — the size of the array.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array.
The third line contains an integer q (1 ≤ q ≤ 4·105) — the number of queries.
The next q lines describe the queries and may have one of the following forms:
- 1 l r x (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 109).
- 2 i y (1 ≤ i ≤ n, 1 ≤ y ≤ 109).
Guaranteed, that there is at least one query of first type.
For each query of first type, output "YES" (without quotes) if Bash's guess is almost correct and "NO" (without quotes) otherwise.
3 2 6 3 4 1 1 2 2 1 1 3 3 2 1 9 1 1 3 2
YES YES NO
5 1 2 3 4 5 6 1 1 4 2 2 3 6 1 1 4 2 1 1 5 2 2 5 10 1 1 5 2
NO YES NO YES
题意：给你一个数组，然后有两种操作，第一种是问一个区间[l,r]的gcd是否几乎是x，什么是几乎是x呢，就是改变[l,r]中最多一个数字使得区间的gcd可以为x（实际上并没有改变这个数字），第二种是改变数组中的一个数字。
思路：本来是想用线段树做区间gcd，然后如果要查询[l,r]，就先判断[l,mid]和[mid+1,r]这两半区间是否最多有一个不是x的倍数，如果两个都不是x的倍数，那么就不可能改变为x；如果两个都是x的倍数，那么这一整段的gcd肯定可以是x；如果有一个不是x的倍数，那么就递归处理这一段。代码如下：
bool judge(int l,int r,int x)
{int m = (l+r)/2;int q1 = query(l,m,1,n,1);int q2 = query(m+1,r,1,n,1);if(q1 % x != 0 && q2 % x != 0)return false;if(q1 % x == 0 && q2 % x == 0)return true;if(l == m || m+1 == r)return true;if(q1 % x != 0)return judge(l,m,x);if(q2 % x != 0)return judge(m+1,r,x);
}
最后换成了直接在query查询线段树的时候就做上面的工作，这样就可以省掉一个log。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;int gcd(int a,int b)
{if(b == 0)return a;elsereturn gcd(b,a%b);
}
const int maxn = 500010;
int sum[maxn*4];void PushUp(int rt)
{sum[rt] = gcd(sum[rt*2],sum[rt*2+1]);
}void build(int l, int r, int rt)
{if (l == r){scanf("%d",&sum[rt]);return;}int m = (l + r) / 2;build(l, m, rt*2);build(m + 1, r, rt*2+1);PushUp(rt);
}
void update(int p,int c, int l, int r, int rt)
{if(l == r){sum[rt] = c;return;}int m = (l + r) / 2;if(p <= m)update(p, c, l, m, rt*2);elseupdate(p, c, m + 1, r, rt*2+1);PushUp(rt);
}
int cnt,x;
void query(int ll, int rr, int l, int r, int rt)
{if(cnt > 1) //记得加这句剪枝return;if(l == r){cnt++;return;}int m = (l + r) / 2;int ret = 0;if(ll <= m && sum[rt*2] % x != 0)query(ll, rr, l, m, rt*2);if(rr > m && sum[rt*2+1] % x != 0)query(ll, rr, m + 1, r, rt*2+1);
}int main(void)
{int n,q,i,j;scanf("%d",&n);build(1,n,1);scanf("%d",&q);while(q--){int op;scanf("%d",&op);if(op == 1){int l,r;scanf("%d%d%d",&l,&r,&x);cnt = 0;query(l,r,1,n,1);if(cnt <= 1)printf("YES\n");elseprintf("NO\n");}else{int p,c;scanf("%d%d",&p,&c);update(p,c,1,n,1);}}return 0;
}
这篇关于Codecraft-18 and Codeforces Round #458 D. Bash and a Tough Math Puzzle（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
