$题目描述$

$给定一行n个正整数a1, a2, ....an。$

$m次询问，每次询问给定一个区间[l, r]，输出 a_l,a_r 的最大公因数。$

$输入格式$

$第一行两个整数n，m。$

$第二行n个整数表示a1, a2, ....an。$

$以下m行，每行2个整数表示询问区间的左右端点。$

$保证输入数据合法。$

$输出格式$

$输出共m行，每行输出一个数。$

样例输入

5 3
4 12 3 6 7
1 3
2 3
5 5

样例输出

1
3
7

$代码呈现：$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e7 + 1;
const int M = 1e5 + 1;
ll Log[N];
ll f[M][20];
ll a[N];
ll n,m;
ll gcd(ll a,ll b){
    return  b ? gcd(b, a % b) : a;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(ll i = 1;i <= n; i++) scanf("%lld",&a[i]);

    Log[0] = -1;// 预处理
    for(ll i = 1;i <= n;i ++) Log[i] = Log[i >> 1] + 1; 
    for(ll i = 1;i <= n;i ++) f[i][0] = a[i];
    for(ll j = 1;j <= Log[n];j ++)
        for(ll i = 1;i + (1 << j) - 1 <= n;i ++)
            f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

    for(ll i = 1;i <= m;i ++) //查询答案
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        ll k = Log[y - x + 1];
        printf("%lld\n",gcd(f[x][k], f[y - (1 << k) + 1][k]));
    }
    return 0;
}