http://codeforces.com/contest/475

D题 CGCDSSQ

大体思路是遍历一下原数组,当遍历到数 a[i] 时,计算 gcd(a[i], 从 a[j]「一路过来」的 gcd) (j<=i)。
注意这个计算过程是一个可以迭代的过程。
由于算出来的 gcd 有极多重复的值,而 a[i] 又很大,所以我们需要用一个 map 保存计算过的值及其个数,然后累加统计。
复杂度是

(只贴出与题目有关的代码,宏定义见 GitHub

map<int, ll> seg_gcd, new_seg_gcd, ans;

int main() {
    int n, x, g;
    SI(n);
    while (n--) {
        SI(x), ++seg_gcd[x];
        new_seg_gcd.clear();
        loop (it, seg_gcd) {
            g = gcd(it->first, x);
            new_seg_gcd[g] += it->second;
            ans[g] += it->second;
        }
        seg_gcd = new_seg_gcd;
    }
    SI(n);
    while (n--) SI(x), PL(ans[x]);
    return 0;
}

Comments

comments powered by Disqus