codeforces 457D CGCDSSQ

全是公式懒得搬了= =

地址

题解

$f[i][x]$表示以$i$为左端点的区间中，$gcd=x$的有多少个。

由右到左进行转移，赋初值$f[i][a_i]=1$：

$f[i][gcd(x,a_i)]=\sum f[i+1][x]$

因为对于以$a_i$为左端点的区间$gcd$，最多只有$log_a_i$种取值（每次$gcd$至少减小一半），所以第二维其实只有$log_a_i$个有值。我们可以用map代替第二维，并滚动第一维。

#include <cstdio>
#include <map>
using namespace std;
map <int, long long> ans, f[2];
map<int,long long>::iterator it;
int n, m, a[100010], T, p;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    f[0][a[n]] = 1, ans[a[n]]++;
    for (int i = n - 1, cur = 0; i >= 1; --i) {
        cur ^= 1, f[cur].clear(), f[cur][a[i]] = 1;
        for (it = f[cur ^ 1].begin(); it != f[cur ^ 1].end(); ++it)
            f[cur][gcd(it->first, a[i])] += it->second;
        for (it = f[cur].begin(); it != f[cur].end(); ++it)
            ans[it->first] += f[cur][it->first];
    }
    scanf("%d", &T);
    while (T--)
        scanf("%d", &p), printf("%lld\n", ans[p]);
}