CF475D-CGCDSSQ

2022-03-08 题解

题目大意：有一个数列，给出q次询问，每次询问是一个数x，问数列中有多少个子段，字段中所有数的最大公约数为x。

解决方法是用ST得到任意区间的最大公约数，代码如下，基本与普通的ST预处理相同

void init()//n:数列长度 a[]:数列
{
    int i, j, t = log2(n);
    for (i = 1; i <= n; i++)
        st[0][i] = a[i];
    for (j = 1; j <= t; j++)
    {
        for (i = 1; i <= n - (1 << j) + 1; i++)
            st[j][i] = __gcd(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    }
}
int sgcd(int l, int r)//子段[l,r]的最大公约数
{
    int t = log2(r - l + 1);
    return __gcd(st[t][l], st[t][r - (1 << t) + 1]);
}

之后以各个元素为头，统计以该元素为头的各个子段的最大公约数。

头元素相同的各个子段中，长度较长的子段，最大公约数小于等于长度短的子段，这就存在了一定的单调性。可以每次可以用二分得到当前头元素下，最大公因数相同的子段的个数。由于不同子段间的最大公因数的大小至少会差2倍，在次数很少（接近 $log_2n$ ）的二分后，就可以得到以一个元素为头元素的所有子段的最大公约数。每次求得时候开一个map统计即可。

#include <bits/stdc++.h>
using namespace std;
int a[100005], st[30][100005], n;
void init()
{
    int i, j, t = log2(n);
    for (i = 1; i <= n; i++)
        st[0][i] = a[i];
    for (j = 1; j <= t; j++)
    {
        for (i = 1; i <= n - (1 << j) + 1; i++)
            st[j][i] = __gcd(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    }
}
int sgcd(int l, int r)
{
    int t = log2(r - l + 1);
    return __gcd(st[t][l], st[t][r - (1 << t) + 1]);
}
map<int, long long> sum;
int ub(int beg, int l, int r, int tar)
{
    int md;
    while (r - l > 1)
    {
        md = ((r - l) >> 1) + l;
        if (sgcd(beg, md) < tar)
            r = md;
        else
            l = md;
    }
    return r;
}
int main()
{
    int q, g, i, j, t;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    init();
    for (i = 1; i <= n; i++)
    {
        j = i;
        while (j <= n)
        {
            g = sgcd(i, j);
            t = ub(i, j, n, g);
            sum[g] += t - j;
            j = t;
            if (sgcd(i, t) == g)
            {
                sum[g]++;
                j++;
            }
        }
    }
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d", &t);
        printf("%lld\n", sum[t]);
    }
    return 0;
}