1#include <iostream>2using namespace std;3int n, m, a[100007], L, R, lg[100007], i, j, t, dp[100007][25], pw[25];4int gcd(int x, int y) {5    if (y == 0) return x;6    return gcd(y, x % y);7}8int main() {9    cin >> n >> m;10    for (i = 1; i <= n; i++) cin >> a[i];11    t = 0;12    pw[0] = 1;13    for (i = 1; i <= 24; i++) pw[i] = pw[i - 1] * 2;14    for (i = 1; i <= 100000; i++)15        if (pw[t + 1] >= i) lg[i] = t;16        else { t++; lg[i] = t; }17    for (i = 1; i <= n; i++) {18        dp[i][0] = a[i];19    }20    for (j = 1; j <= lg[n]; j++) {21        for (i = 1; i + pw[j] - 1 <= n; i++) {22            dp[i][j] = gcd(dp[i][j - 1], dp[i + pw[j - 1]][j - 1]);23        }24    }25    for (i = 1; i <= m; i++) {26        cin >> L >> R;27        cout << gcd(dp[L][lg[R - L + 1]], dp[R - pw[lg[R - L + 1]] + 1][lg[R - L + 1]]) << endl;28    }29    return 0;30}

说明：保证 $1 \le n \le 100000$，每次查询满足 $1 \le L \le R \le n$，且数组 $a$ 的元素均为正整数。