题目链接:https://ac.nowcoder.com/acm/contest/877/F
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述
输入描述

输出描述

输入

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

解题思路

题意:有两种操作:0代表将[l, r]之间的数变成√ai, 1代表求出[l, r]中所有数的最大公约数。
思路:线段数，因为1开根号还是1，故可以把结果为1的标记上，避免无用的计算。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
struct edge {
    bool Mark;
    long long val;
}segTree[MAXN << 2];
void Create(int root, int left, int right) {
    segTree[root].Mark = 0;
    if (left == right) {
        scanf("%lld", &segTree[root].val);
        return ;
    }
    int mid = left + ((right - left) >> 1);
    Create(root << 1, left, mid);
    Create(root << 1 | 1, mid + 1, right);
    segTree[root].Mark = segTree[root << 1].Mark && segTree[root << 1 | 1].Mark;
    segTree[root].val = __gcd(segTree[root << 1].val, segTree[root << 1 | 1].val);
}
void Update(int root, int Q_left, int Q_right, int left, int right) {
    if (segTree[root].Mark)
        return ;
    if (left == right) {
        segTree[root].val = sqrt(segTree[root].val);
        if (segTree[root].val == 1)
            segTree[root].Mark = 1;
        return ;
    }
    int mid = left + ((right - left) >> 1);
    if (Q_right <= mid)
        Update(root << 1, Q_left, Q_right, left, mid);
    else if (Q_left > mid)
        Update(root << 1 | 1, Q_left, Q_right, mid + 1, right);
    else {
        Update(root << 1, Q_left, mid, left, mid);
        Update(root << 1 | 1, mid + 1, Q_right, mid + 1, right);
    }
    segTree[root].Mark = segTree[root << 1].Mark && segTree[root << 1 | 1].Mark;
    segTree[root].val = __gcd(segTree[root << 1].val, segTree[root << 1 | 1].val);
}
long long Query_(int root, int Q_left, int Q_right, int left, int right) {
    if (Q_left <= left && Q_right >= right)
        return segTree[root].val;
    int mid = left + ((right - left) >> 1);
    if (Q_right <= mid)
        return Query_(root << 1, Q_left, Q_right, left, mid);
    else if (Q_left > mid)
        return Query_(root << 1 | 1, Q_left, Q_right, mid + 1, right);
    else return __gcd(Query_(root << 1, Q_left, mid, left, mid),
            Query_(root << 1 | 1, mid + 1, Q_right, mid + 1, right));
}
int main() {
    int n, m, left, right, Judge;
    scanf("%d", &n);
    Create(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        scanf("%d%d%d", &Judge, &left, &right);
        if (Judge)
            printf("%lld\n", Query_(1, left, right, 1, n));
        else Update(1, left, right, 1, n);
    }
    return 0;
}