AtCoder Regular Contest 023 D - GCD区間

問題

arc023.contest.atcoder.jp

解法

まず少し考察です。区間 [s, t] にある最大公約数は, s が t から 0 に動くにつれて単調減少します。そして, その最大公約数の減少の仕方は, 素因数が 少しずつ減少していくことで生じます(例えば 6 -> 3 -> 1 と最大公約数が減少したとすると, これは素因数 2 がなくなる -> 素因数 3 がなくなる, という感じで最大公約数が減っています)。

では, 区間 [s, t] にある最大公約数は, s が t から 0 に動く場合に何通りほど考えられるかというと, およそ 30 であることがわかります(10^9 はだいたい 2^30 のため。「2 が 30 個」という状況以上に素因数の数は増えない)。

ということで, 解法です。クエリは無視して, 入力が与えられたら最大公約数の候補ごとにいくつの GCD 区間があるかを数えていきます。
では, GCD 区間はどう数えるかというと, 各 t について, 区間 [0, t] にある最大公約数のリスト及びその数を数えていくことでこれを行います。これは, 区間 [0, t-1] にある最大公約数のリストを使うと, 簡単に出来ます。

例を挙げます。例えば, 2, 6, 3, 4 という数列を考えると, 一番最初では, GCD リストは [(2, 1)] です(左が GCD, 右がその GCD の個数を表す)。次に 6 まで進むと, [(2, 1), (6, 1)] となります。次に 3 では [(1, 1), (3, 2)] となり, 最後に 4 まで進むと [(1, 3), (4, 1)] となります。

あとはコードを参考に…

map<ll, ll> pre, ans;

const int MAXN = 100010;
ll a[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int t = 0; t < n; t++) {
        map<ll, ll> now;
        for (auto p : pre) now[__gcd(a[t], p.first)] += p.second;
        now[a[t]] += 1;
        for (auto p : now) ans[p.first] += p.second;
        pre = now;
    }

    while (m--) {
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }
    return 0;
}