CF475D CGCDSSQ 题解

题意：

给出一个长度为 \(n\) 的序列和 \(q\) 个询问，

每个询问输出一行，询问满足 \(\gcd\{a_l,a_{l+1},\dots,a_r\}=x\) 的 \([l,r]\) 的对数

\(1 \le n \le 10^5,~1 \le q \le 3 \times 10^5,~1 \le a_i,x_i \le 10^9\)

这题有一个很有趣的结论。

区间 \(\gcd\) 最多有 \(\mathcal{O}(n\log \omega)\) 种可能的值（记 \(\omega = \max\{a_i\}\)）

即 \(l\) 固定时，\([l,r]\) 的区间 \(\gcd\) 至多有 \(\mathcal{O}(\log \omega)\) 种取值。

证明：

假设区间 \(\gcd\) 在 \(i\) 处发生了变化，此时新的 \(\gcd\) 一定是原 \(\gcd\) 的因数

因此新的 \(\gcd\) 至少缩小了一半，则至多有 \(\mathcal{O}(\log \omega)\) 种取值。

这样我们就可以预处理所有答案，用个unordered_map记录了

注：这里其实可以优化一下，不用记录所有答案，只记录询问的答案

那么答案怎么统计呢？

区间 \(\gcd\) 直接用 \(\mathtt{st}\) 表维护，应该很容易想到。

当 \(l\) 固定时，至多有 \(\mathcal{O}(\log \omega)\) 种取值，而这个值一定随着右端点的增大单调不升。

因此考虑二分右端点，然后记录下答案啥的

注意 \(\mathtt{st}\) 表一定要预处理查询时候的lg[]数组，因为log()常数比较大

时间复杂度 \(\mathcal{O}(n\log n + n\log \omega)\)

\(\mathtt{ST}\) 表处理 \(\gcd\) 复杂度为 \(\mathcal{O}\left(n (\log n + \log\omega)\right)\)

证明：详见参考文献[1]

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
    template <typename T> void print(T x) { write(x); pc('\n'); }
}using namespace FastIO;
#define N ((int)(1e5+15))
#define M ((int)(3e5+15))

unordered_map<int,int> ans,vis;
int n,m,a[N],q[M],lg2[N],f[N][20];
int gcd(int a,int b) { return b == 0 ? a : gcd(b,a%b); }
void change(int u,int x)
{
    f[u][0] = x;
    for(int i=1; (1 << i) <= u; i++)
        f[u][i] = gcd(f[u][i-1], f[u - (1 << (i-1))][i-1]);
}
int query(int l,int r)
{
    int k = lg2[r-l+1];
    return gcd(f[l + (1 << k) - 1][k], f[r][k]);
}
int find(int g,int l,int i)
{
    for(int r=n; l<r; )
    {
        int mid = (l + r + 1) >> 1;
        if(query(i,mid) == g) l = mid;
        else r = mid - 1;
    }
    return l;
}
void solve(int i)
{
    for(int last, now=i, g=a[i]; ; )
    {
        last = now; now = find(g, now, i);
        if(vis[g]) ans[g] += now - last + 1;
        if(now == n) return; g = query(i,++now);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); lg2[0] = -1;
    for(int i=1; i<=n; i++)
    {
        read(a[i]); change(i,a[i]);
        lg2[i] = lg2[i >> 1] + 1;
    }
    read(m);
    for(int i=1; i<=m; i++)
        { read(q[i]), vis[q[i]] = 1; }
    for(int i=1; i<=n; i++) solve(i);
    for(int i=1; i<=m; i++) print(ans[q[i]]);
    return 0;
}