D. CGCDSSQ

题目链接：Problem - 475D - Codeforces

题目大意：给定n长度的序列a, 现有q次查询机会， 每一次的查询x,  输出有多少个区间的gcd等于x

输入：

输入的第一行包含整数 n 、( 1 ≤ n ≤ 1e5 )，表示序列的长度。下一行包含 n 空格分隔的整数 a1, ..., an , ( 1 ≤ ai ≤ 1e9 )。

输入的第三行包含整数 q , ( 1 ≤ q ≤ 3 × 1e5 ), 表示查询次数。然后是 q 行，每行包含一个整数 xi , ( 1 ≤ xi ≤ 1e9 )。

运用的方法： ST表， 二分， STL map;

1.对于要查询区间查询gcd, 就会想到采用特殊的数据结构， ST表， 线段树等等。此处采用ST表维护。

3.建立gcd的ST表

3.由于要数出区间gcd等于x的数量，想到暴力枚举左边界 i, 并且l = i, 让 l 不断的向n靠拢， 每一次二分右边界， （二分到恰好让gcd改变的位置， 假设g为当前的gcd），统计答案 mp[ g ] += r - l + 1(子区间问题); l = r+1, 然后求当前 i 到 l 的gcd, 再二分最小右边界。 直到 l > n.

4.最后查询答案， 注意答案开 long long;

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128;
using ui64 = unsigned long long;
//STGCD, 二分
const int N = 1e5+5;
int stgcd[N][33];
int lg2[N];
int n;
void build(){//建立ST表
    for(int p=1; p<=lg2[n]; p++) {
        for(int i=1; i + (1<<p) - 1<=n; i++) {
            stgcd[i][p] = gcd(stgcd[i][p-1], stgcd[i+(1<<(p-1))][p-1]);
        }
    }
}
int query(int l, int r){
    int p = lg2[r-l+1];
    return gcd(stgcd[l][p], stgcd[r-(1<<p)+1][p]);
}
int go(int i,int l, int r, int g){
    while(l<=r) {
        int mid = (l+r)>>1;
        int tg = query(i, mid);//查询的是i到r
        if(tg == g) {
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    return l-1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    lg2[0] = -1;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        lg2[i] = lg2[i>>1] + 1;
        stgcd[i][0] = a[i];
    }

    build();

    map<int,i64> cnt;
    for(int i=1; i<=n; i++) {
        int l = i;//1e5暴力枚举
        while(l<=n) {
            int g = query(i, l);
            int r = go(i, l, n, g);
            cnt[g] += r-l+1;
            l = r+1;//枚举边界
        }
    }
    int m;
    cin >> m;
    while(m--) {
        int x;
        cin >> x;
        cout << cnt[x] << "\n";
    }
    return 0;
}

感谢各位的收看与点赞， 欢迎大佬指正。