题目描述

难度分:$2100$

输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

然后输入$q(1 \leq q \leq 10^5)$和$q$个询问，每个询问输入两个数$L$和$R$，表示下标从$L$到$R$的连续子数组$(1 \leq L \leq R \leq n)$。

对于每个询问，输出$R-L+1-C$，其中$C$为子数组中的元素$x$的个数，满足$x$能整除子数组中的每个数。

输入样例

5
1 3 2 4 2
4
1 5
2 5
3 5
4 5

输出样例

4
4
1
1

算法

数学+$ST$表

构建一个$ST$表用于查询区间的最大公约数$gcd$；构建一个映射$val2pos$表示“数值$\rightarrow$这个数值在数组$a$中出现的索引列表（升序）”。

对于一个询问$[L,R]$，其中能被区间内所有数整除的整数一定是区间最大公约数$g$。在$val2pos[g]$上进行二分查找，确定落在区间$[L,R]$内的索引有多少个，这些索引的个数就是区间$[L,R]$内可以整除所有元素的整数个数$C$。

复杂度分析

时间复杂度

预处理出$ST$表的时间复杂度为$O(nlog_2n)$。处理每个询问$[L,R]$时，需要对每个索引列表二分查找，时间复杂度是$O(log_2n)$，处理$O(q)$条询问的时间复杂度为$O(qlog_2n)$。

综上，整个算法的时间复杂度为$O((n+q)log_2n)$。

空间复杂度

映射$val2pos$中存的也是$a$的$O(n)$个索引，所以空间复杂度为$O(n)$。$ST$表的空间消耗是$O(nlog_2n)$。

因此，空间消耗的瓶颈在于$ST$表，整个算法的额外空间复杂度为$O(nlog_2n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, M = 20;
int n, q, a[N], st[N][M];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int query(int l, int r) {
    int k = log2(r - l + 1);
    return __gcd(st[l][k], st[r - (1<<k) + 1][k]);
}

int main() {
    int n;
    scanf("%d", &n);
    unordered_map<int, vector<int>, custom_hash> val2pos;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        val2pos[a[i]].push_back(i);
    }
    for(int j = 0; j < M; j++) {
        for(int i = 1; i + (1 << j) - 1 <= n; i++) {
            if(!j) {
                st[i][j] = a[i];
            }else {
                st[i][j] = __gcd(st[i][j - 1], st[i + (1<<(j - 1))][j - 1]);
            }
        }
    }
    scanf("%d", &q);
    while(q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int g = query(l, r);
        if(!val2pos.count(g)) {
            printf("%d\n", r - l + 1);
        }else {
            auto&pos = val2pos[g];
            int low = lower_bound(pos.begin(), pos.end(), l) - pos.begin();
            int high = upper_bound(pos.begin(), pos.end(), r) - pos.begin();
            int C = high - low;
            printf("%d\n", r - l + 1 - C);
        }
    }
    return 0;
}