# GCD Problem（线段树区间GCD+区间开方）

```4
5 45 20 65
7
1 1 4
0 1 4
1 1 4
1 3 4
0 3 4
1 3 4
1 2 2```

```5
2
4
2
6```

两个操作，一个是区间开方，一个是输出区间GCD；gcd很好处理。主要是开放这个操作，假设区间sum==l-r+1就return，不是的话就取找辣个还不是1的点去单点更新，这样最多更新nlogn*8次左右（可能没算错~）~~就行了

``````#includebits/stdc++.h
using namespace std;
#define lson l,m,rt1
#define rson m+1,r,rt1|1
#define ll long long
const int maxn = 2e5 + 10;
ll gcd[maxn  2], sum[maxn  2];
long long GCD(long long a, long long b) {
return b ? GCD(b, a%b) : a;
}
void pushup(int rt) {
sum[rt] = sum[rt  1] + sum[rt  1 | 1];
gcd[rt] = GCD(gcd[rt  1], gcd[rt  1 | 1]);
}
void build(int l, int r, int rt) {
if (l == r) {
scanf("%lld", sum[rt]);
gcd[rt] = sum[rt];
return;
}
int m = (l + r)  1;
build(lson); build(rson);
pushup(rt);
}
void updates(int L, int R, int l, int r, int rt) {
if (sum[rt] == r - l + 1)return;
if (l == r) {
sum[rt] = sqrt(sum[rt]);
gcd[rt] = sum[rt];
return;
}
int m = (l + r)  1;
if (L = m)updates(L, R, lson);
pushup(rt);
}
ll query(int L, int R, int l, int r, int rt) {
if (L = lr = R) {
return gcd[rt];
}
int m = (l + r)  1;
ll ans;
if (L = m) {
ans = query(L, R, lson);
if (m  R)
ans = GCD(ans, query(L, R, rson));
}
else ans = query(L, R, rson);
return ans;
}
int main() {
int n;
scanf("%d", n);
build(1, n, 1);
int q; scanf("%d", q);
while (q--) {
int a, b, c;
scanf("%d%d%d", a, b, c);
if (a == 1) {
printf("%lld\n", query(b, c, 1, n, 1));
}
else {
}
}
return 0;
}``````

• 星秀
• 音乐
• 王者荣耀
• 1:32:00