rangegcd

#include <stdio.h>

int ST[300000][20], lg[300000];

int nod(int a, int b) {
    while (a && b) {
        if (a >= b) a %= b;
        else b %= a;
    }
    return a | b;
}

int query(int l, int r, int lg[]) {
    int j = lg[r - l + 1];
    return nod(ST[l][j], ST[r - (1 << j) + 1][j]);
}

void build(int a[], int lg[], int n) {
    for (int i = 0; i < n; ++i) ST[i][0] = abs(a[i]);
    for (int j = 1; j <= lg[n]; ++j) {
        for (int i = 0; i <= (n - (1 << j)); ++i) {
            ST[i][j] = nod(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int main() {
    int n, k, l, r;
    scanf("%d", &n);
    int a[n];
    lg[1] = 0;
        for (int i = 2; i <= n; ++i) {
                lg[i] = lg[i / 2] + 1;
        }
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &k);
    build(a, lg, n);
    for (int i = 0; i < k; ++i) {
        scanf("%d %d", &l, &r);
                printf("%d\n", query(l, r, lg));
    }
    return 0;
}

____________________________________________________________________________________________________________________________

Наибольший общий делитель подпоследовательности

Составьте программу rangegcd.c, вычисляющую наибольший общий делитель на различных интервалах последовательности целых чисел.

Формат входных данных
Первая строка, считываемая со стандартного потока ввода, содержит размер последовательности n (0 < n ≤ 300000). Во второй строке перечислены элементы последовательности. Каждый элемент представляет собой целое число, находящееся в диапазоне от -109 до 109. Элементы разделяются пробелами.
Третья строка содержит общее количество запросов m (0 < m ≤ 1000000). Каждая из следующих m строк содержит запрос, который представляет собой два числа l и r, задающие границы интервала, на котором нужно вычислить наименьший общий делитель (0 ≤ l,r < n).
Формат результата работы программы
Для каждого запроса вывести в стандартный поток вывода наименьший общий делитель указанной подпоследовательности.
Пример работы программы

Ввод:
10
-10 -2 5 60 80 100 77 65 33 45
6
0 9
0 1
2 5
3 5
6 8
8 9
Вывод:
1
2
5
20
1
3