AtCoder Regular Contest 023 D - GCD区間

問題概要

長さ $n (\leq 10^5)$ の数列 $a_1, a_2 \dots, a_N (1 \leq a_i \leq 10^9)$ がある。この数列に対して，次のクエリが $m (\leq 10^5)$ 回与えられる。それぞれのクエリの答えを出力せよ。

最大公約数が $x$ となる区間はいくつある？

解法概要

$a_l, a_{l+1} \dots, a_{r-1}, a_r$ の最大公約数を $\mathit{gcd}(l, r)$ と表す。

区間の数は全部で $n^2-1$ 個あるので，区間$[s, t]$ の $s$ と $t$ をすべて愚直に試していると当然間に合わない。

しかし，$t = T$ と $t$ を固定したとき，区間$[s, T](1 \leq s \leq T)$について，$\mathit{gcd}(s, T)$ の値としてありうるものは30個未満になる。何故ならば，$2^{30} \ge 10^9$ より数列の各要素が持つ素因数も30個未満であるため，要素同士の最大公約数の素因数も30個未満になるからである。$t = T$ で，$s$ を$T$ から $1$ へと減らしていくにつれて，その区間の最大公約数から素因数が徐々に削られていくイメージ。

したがって，$t$ の値ごとに，$\mathit{gcd}(s, t) (1 \leq s \leq t)$ の値の出現回数を map などに保持しながら数えればよい。実装の上では，$t = T$ のときに「$\mathit{gcd}(s, T-1) (1 \leq s \leq T-1)$ と $a_T$ から $\mathit{gcd}(s, T)$ を求めること」と「$\mathit{gcd}(T, T)$ の値 (必ず $a_T$を数えること」をしておけばよい。$\mathit{gcd}(s, T-1)$ が30種類未満なので，この前処理部分の時間計算量はループ分の $\mathcal{O}(n \log \max_i a_i)$ と map の値の参照分の $\mathcal{O}(\log \max_i a_i)$ で$\mathcal{O}(n (\log \max_i a_i)^2)$。

区間の終端のインデックスが $t$ でかつ最大公約数が $x$ の区間の数を $\mathit{cnt}_{t, x}$ とすると，クエリで答えるべきは $\sum_{t = 1}^n \mathit{cnt}_{t, x}$。クエリごとに毎回足し算をしていては間に合わないので，$x$ の値ごとに事前に足し合わせておく。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

using ll = long long;

ll gcd(ll a, ll b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    for(int i=0;i<n;++i) cin >> a[i];

    map<ll, ll> mp[n];
    mp[0][a[0]] = 1;
    for(int t=1;t<n;++t) {
        for(auto itr=mp[t-1].begin();itr!=mp[t-1].end();++itr) {
            mp[t][gcd(itr->first, a[t])] += itr->second;
        }
        ++mp[t][a[t]];
    }
    for(int t=0;t<n-1;++t) {
        for(auto itr=mp[t].begin();itr!=mp[t].end();++itr) {
            mp[n-1][itr->first] += itr->second;
        }
    }

    ll  x;
    for(int i=0;i<m;++i) {
        cin >> x;
        cout << mp[n-1][x] << endl;
    }
}

所感

gcd として取りうる値が少ないことを使った考察がなかなか身につかない。