题目链接 

题意  给定一个序列，两种询问：单点修改，询问某个区间能否通过改变最多一个数使得该区间的$gcd$值为$val$。

问题转化为询问某个区间里不是val的倍数的数的个数是否不超过$1$。

用线段树实现即可。

#include 
     
      using namespace std;#define rep(i, a, b)	for (int i(a); i <= (b); ++i)#define dec(i, a, b)	for (int i(a); i >= (b); --i)const int A = 20;int t[1 << A];int n, q, k, actn;inline int query(int i, int l, int r, int L, int R, int val){	if (t[i] % val == 0) return 1;	if (i >= n){		if (!--k) return 0;		return 1;	}	int mid = (l + r) >> 1;	if (L <= mid){		if (!query(i << 1    , l      , mid    , L              , min(mid, R) , val)) return 0;	}	if (R  > mid){		if (!query(i << 1 | 1, mid + 1, r      , max(mid + 1, L), R           , val)) return 0;	}	return 1;}inline void update(int x, int val){	t[x += n] = val;	for (; x >>= 1;) t[x] = __gcd(t[x << 1], t[x << 1 | 1]);}	int main(){	scanf("%d", &actn);	n = 1 << 19;		rep(i, 0, actn - 1){		int x;		scanf("%d", &x);		t[i + n] = x;	}	dec(i, n - 1, 1) t[i] = __gcd(t[i << 1], t[i << 1 | 1]);		scanf("%d", &q);	while (q--){		int op;		scanf("%d", &op);		if (op == 1){			int x, y, z;			scanf("%d%d%d", &x, &y, &z);			k = 2;			puts(query(1, 0, n - 1, x - 1, y - 1, z) ? "YES" : "NO");		}		else{			int x, y;			scanf("%d%d", &x, &y);			update(x - 1, y);		}	}	return 0;}