题解 P1890 【gcd区间】

奔波儿霸 · 2018-08-23 06:42:29 · 题解

都是扯淡

看到题解里面竟然没有人写分块。。。

鉴于我最近一直在学习分块大法，所以就发一篇分块的题解吧。

还有这题简直就是分块好题啊

解题思路

如果你不会分块的话，请去做一下黄学长的数列分块入门1-9。他的blog里面也有题解，写的很好哦。

下面我们来看这道题咋做，因为根本就不需要修改，所以直接不用考虑如何维护真良心QAQ。

将每个块都求一个\gcd，然后询问的时候对于两边多出来的不完整块，我们暴力的进行求\gcd，然后在和每个块的\gcd取\gcd。将最后的答案输出。

附上代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
const int maxn = 1e6+3;
typedef long long LL;
int n, cnt, arr[maxn], GCD[1003], a, b, m, in[1003];
inline int gcd(int x, int y) {
    return y ? (gcd(y, x%y)) : x;
}
inline LL read() {
    LL x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while (c <= '9' && c >= '0') {x = x*10 + c-'0'; c = getchar();}
    return x * f;
}
inline int query(int l, int r) {
    int ans = arr[l];
    for(int i=l; i<=std::min(r, in[l]*cnt); i++)
        ans = gcd(ans, arr[i]);
    if(in[l] != in[r])
        for(int i=(in[r]-1)*cnt+1; i<=r; i++)
            ans = gcd(ans, arr[i]);
    for(int i=in[l]+1; i<in[r]; i++)
        ans = gcd(ans, GCD[i]);
    return ans;
}
int main() {
    n = read(), m = read();
    cnt = std::sqrt(n);
    for(int i=1; i<=n; i++) {
        arr[i] = read();
        in[i] = (i-1)/cnt+1;
        GCD[in[i]] = !GCD[in[i]] ? arr[i] : gcd(GCD[in[i]], arr[i]);
    }
    for(int i=1; i<=m; i++) {
        a = read(), b = read();
        printf("%d\n", query(a, b));
    }
    return 0;
}