# ARC023-D GCD区間 (解説AC)

試験管2511diff
https://atcoder.jp/contests/arc023/tasks/arc023_4

## 解法

gcdが減るときは、$\frac{1}{2}$以下になるので、減少する回数はたかだか$\log_{2}10^9$回 -> 同じ区間をまとめて計算する

## 実装

#include <bits/stdc++.h>

struct SparseTable {
    std::vector<int> L;
    std::vector<std::vector<int>> dat;
    SparseTable(std::vector<int> A) : L(A.size() + 1), dat() {
        for (int i{1} ; i < (int)L.size() ; i++) {
            L[i] = L[i - 1] + (i >> (L[i - 1] + 1));
        }
        dat.resize(L.back() + 1);
        dat[0] = A;
        for (int i{1}, len{2} ; i < (int)dat.size() ; i++, len <<= 1) {
            dat[i] = dat[i - 1];
            for (int j{} ; j + len - 1 < (int)dat[i].size() ; j++) {
                dat[i][j] = std::gcd(dat[i - 1][j], dat[i - 1][j + (len >> 1)]);
            }
        }
    }
    int product(int l, int r) const {
        assert(0 <= l and l <= r and r <= (int)dat[0].size());
        int now{L[r - l]};
        return (l == r ? 0 : std::gcd(dat[now][l], dat[now][r - (1 << now)]));
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N, M;
    std::cin >> N >> M;
    std::vector<int> A(N);
    for (auto& a : A) std::cin >> a;
    SparseTable spt{A};
    std::vector<std::pair<int, int>> kiyo;
    std::vector<int> app;
    kiyo.reserve(30 * N);
    app.reserve(30 * N);
    for (int i{} ; i < N ; i++) {
        // std::cout << "start " << i + 1 << std::endl;
        for (int j{i}, cur{A[i]} ; j < N ; ) {
            if (cur == 1) {
                kiyo.push_back(std::pair{ cur, N - j });
                app.push_back(cur);
                // map[cur] += N - j;
                break;
            }
            else {
                int ok{j + 1}, ng{N + 1};
                while (ng - ok > 1) {
                    int mid{(ok + ng) / 2};
                    if (cur == spt.product(i, mid)) {
                        ok = mid;
                    }
                    else {
                        ng = mid;
                    }
                }
                kiyo.push_back(std::pair{ cur, ok - j });
                app.push_back(cur);
                j = ok;
                cur = spt.product(i, std::min(N, j + 1));
            }
            // else {
            //     kiyo.push_back(std::pair{ cur, next[j] - j });
            //     app.push_back(cur);
            //     // map[cur] += next[j] - j;
            //     cur = spt.product(i, std::min(N, next[j] + 1));
            // }
        }
    }
    std::sort(app.begin(), app.end());
    app.erase(std::unique(app.begin(), app.end()), app.end());
    std::vector<long long> sum(app.size());
    for (auto [g, num] : kiyo) {
        sum[std::lower_bound(app.begin(), app.end(), g) - app.begin()] += num;
    }
    while (M--) {
        int x;
        std::cin >> x;
        auto it{std::lower_bound(app.begin(), app.end(), x)};
        std::cout << (it == app.end() or app[it - app.begin()] != x ? 0LL : sum[it - app.begin()]) << '\n';
    } 
}

[提出](https://atcoder.jp/contests/arc023/submissions/58600344)

## 感想

CF-Div3のボスでこういう考察をしたことがあったが、今回は引き出せなかった。残念。

ICPCではデータ構造系の問題を担当をしているため、クエリ問題はガンガン解説開いてインプットしていこうと思う。
- 数え上げも担当しているんだけど、今の所数え上げはいい感じに自力で解けてて嬉しい