【YBTOJ】【Luogu P1890】gcd区间

链接：

洛谷

题目大意：

每次询问给定一个区间 ([L,R]) ，输出 (a_{[L,R]}) 的最大公因数。

正文：

ST 表板子题。

代码：

const int N = 1000010;

inline ll Read() 
{
    ll x = 0, f = 1;
    char c = getchar();
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-')
        f = -f, c = getchar();
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return x * f;
}

ll Gcd[N][21];

ll gcd(ll a, ll b) {return b? gcd(b, a % b): a;}

ll Q(int l, int r) 
{
    int k = log2(r - l + 1);
    return gcd(Gcd[l][k], Gcd[r - (1 << k) + 1][k]);
}
int main() {
    int N = Read(), M = Read();
    for (int i = 1; i <= N; i++) Gcd[i][0] = Read();
    for (int j = 1; j <= 21; j++)
        for (int i = 1; i + (1 << j) - 1 <= N; i++)
            Gcd[i][j] = gcd(Gcd[i][j - 1], Gcd[i + (1 << (j - 1))][j - 1]);
    for (int i = 1; i <= M; i++) 
	{
        int l = Read(), r = Read();
        printf("%lld
", Q(l, r));
    }
    return 0;
}