数列互质题解_牛客博客

~~该题之理论题解，代码打炸了(wa了)，就不放了qwq~~
后来debug出来了，统计排序后第一个询问的答案时，我把1写成i了qwq

首先，我们明显的，我们需要使用莫队算法来维护每个颜色的出现次数，设c[i]表示区间中i出现了多少次，同时我们再维护一个数组d[i]表示出现次数为i的有几个颜色。这两个数组在莫队的每次区间更改中都可以O(1)同时维护，所以如果仅仅维护两个数组的话，复杂度是可行的 $O(n\sqrt{n})$

那么，现在我们假设维护了这两个数组，我们该怎么统计答案呢？

我们使用类似数据分块的方式，将出现次数分为两部分：
1.出现次数小于等于 $\sqrt{n}$ ，因为个只有 $\sqrt{n}$ 个，暴力枚举计算即可（使用d数组统计答案）

2.出现次数大于 $\sqrt{n}$ ,这里有个小trick：

一段区间内，出现次数大于 $\sqrt{n}$ 的点的个数是小于 $\sqrt{n}$ 个的，这个大家应该都会证明，就不再说了，那么，我们可以考虑，将这些出现次数大于 $\sqrt{n}$ 的颜色直接储存起来，之后再遍历一遍统计答案即可。

那么现在就有个问题了，因为区间变动的时候，部分颜色的出现次数会发生改变，那么，可能会使得部分原本出现次数大于 $\sqrt{n}$ 的颜色的出现次数小于 $\sqrt{n}$ 了，那么我们就要把它给删去。

那么，现在就主要有两种思路（分别对应我前期和后期的想法）：

一.用stl，比如set维护增加和删除，因为判互质的时候要使用gcd函数，带个log，所以我们使用操作复杂度为log的stl对总复杂度是没影响的。

二.用栈之类直接维护
因为每次区间移动后，我们增加的出现次数大于 $\sqrt{n}$ 的颜色最多 $\sqrt{n}$ 个左右，那么，我们的栈的元素每次最多也就增加 $\sqrt{n}$ 个，加上原来的 $\sqrt{n}$ 个，个数平均就是 $\sqrt{n}$ 级别的，而我们每次又要遍历一遍这些数，那么我们可以把符号条件的数计算答案后加入另一个栈，这样，另一个栈就变成了都是符合条件的元素的情况了，我们把现在的栈O(1)(top=0)清空掉，就相当于询问开始的时候两个栈交换了一下，所以我们可以用类似01滚动的方法，每次用两个栈来分别维护即可~（平均复杂度 $O(\sqrt{n})$ ）

所以总复杂度为 $O(n\sqrt{n}log(n)(log为求gcd的复杂度))$

Update：
一个复杂度上的优化

我们一开始，先做一遍线性筛/埃式筛，做出函数g[x]，g[x]为x的最小/任意一个质因子。

那么，每次询问时查询时，我们就可以先对k进行质因数分解，把k的所有质因子求出来，分别设为 $p_1,p_2...p_k$ ,不难发现，这最多只有7个，于是，我们只需要判断每个询问的数是否是这些数的倍数即可，无需求gcd,复杂度变为: $O(a*n\sqrt{n})(a<=7)=O(n\sqrt{n})$
这是复杂度上的优化，至于实现时产生的常数，则不在我们的考虑之中qwq

代码 $O(n\sqrt{n}logn)$ [1003ms]:

#include<bits/stdc++.h>
using namespace std;
const int N=50001;
int a[N],b[N],c[N],d[N],ans[N];
int e,block,top;
int sta[N],stp[N];
bool vis[N];
struct Que{
    int l,r,k,x;
}q[N];
inline bool kkk(Que x,Que y){
    return b[x.l]!=b[y.l]?b[x.l]<b[y.l]:((b[x.l]&1)?b[x.r]<b[y.r]:b[x.r]>b[y.r]);
}
inline void Insert(int x){
    --d[c[x]];
    ++c[x];
    ++d[c[x]];
    if(c[x]==block+1){
        if(!vis[x]){
            vis[x]=1;sta[++top]=x;
        }
    }
}
inline void Delted(int x){
    --d[c[x]];
    --c[x];
    ++d[c[x]];
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    block=sqrt(n+m);
    for(int i=1;i<=n;++i){
        b[i]=(i-1)/block+1;
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
        q[i].x=i;
    }
    sort(q+1,q+m+1,kkk);
    int L=q[1].l,R=q[1].r;
    for(int i=L;i<=R;++i){
        Insert(a[i]);
    }
    for(int i=1;i<=n;++i){
        if(__gcd(q[1].k,i)==1){
            ans[q[1].x]+=d[i];
        }
    }
    for(int i=2;i<=m;++i){
        while(L>q[i].l){
            Insert(a[--L]);
        }
        while(R<q[i].r){
            Insert(a[++R]);
        }
        while(L<q[i].l){
            Delted(a[L++]);
        }
        while(R>q[i].r){
            Delted(a[R--]);
        }
        for(int j=1;j<=block;++j){
            if(__gcd(j,q[i].k)==1){
                ans[q[i].x]+=d[j];
            }
        }
        int tot=0;
        for(int j=1;j<=top;++j){
            if(c[sta[j]]>block){
                stp[++tot]=sta[j];
                if(__gcd(c[sta[j]],q[i].k)==1){
                    ++ans[q[i].x];
                }
            }else{
                vis[sta[j]]=0;
            }
        }
        top=tot;
        for(int j=1;j<=tot;++j){
            sta[j]=stp[j];
        }
    }
    for(int i=1;i<=m;++i){
        printf("%d\n",ans[i]);
    }
    return 0;
}

代码 $O(n\sqrt{n})$ [235ms]:

#include<bits/stdc++.h>
using namespace std;
const int N=50001;
int a[N],b[N],c[N],d[N],ans[N];
int e,block,top,cnt;
int sta[N],stp[N],g[N],zhi[N];
int sp[N],al;
bool vis[N];int vit[N];
struct Que{
    int l,r,k,x;
}q[N];
inline bool kkk(Que x,Que y){
    return b[x.l]!=b[y.l]?b[x.l]<b[y.l]:((b[x.l]&1)?b[x.r]<b[y.r]:b[x.r]>b[y.r]);
}
inline void Insert(int x){
    --d[c[x]];
    ++c[x];
    ++d[c[x]];
    if(c[x]==block+1){
        if(!vis[x]){
            vis[x]=1;sta[++top]=x;
        }
    }
}
inline void sai(){
    for(int i=2;i<N;++i){
        if(!g[i]){
            g[i]=i;
            zhi[++cnt]=i;
        }
        for(int j=1;j<=cnt;++j){
            if(i*zhi[j]>=N){
                break;
            }
            g[i*zhi[j]]=zhi[j];
            if(i%zhi[j]==0){
                break;
            }
        }
    }
}
inline void Delted(int x){
    --d[c[x]];
    --c[x];
    ++d[c[x]];
}
int main(){
    sai();
    int n,m;
    scanf("%d%d",&n,&m);
    block=sqrt(n+m);
    for(int i=1;i<=n;++i){
        b[i]=(i-1)/block+1;
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
        q[i].x=i;
    }
    sort(q+1,q+m+1,kkk);
    int L=q[1].l,R=q[1].r;
    for(int i=L;i<=R;++i){
        Insert(a[i]);
    }
    for(int i=1;i<=n;++i){ 
        if(__gcd(q[1].k,i)==1){
            ans[q[1].x]+=d[i];
        }
    }
    for(int i=2;i<=m;++i){
        while(L>q[i].l){
            Insert(a[--L]);
        }
        while(R<q[i].r){
            Insert(a[++R]);
        }
        while(L<q[i].l){
            Delted(a[L++]);
        }
        while(R>q[i].r){
            Delted(a[R--]);
        }
        al=0;
        while(g[q[i].k]){
            if(vit[g[q[i].k]]!=i){
                vit[g[q[i].k]]=i,sp[++al]=g[q[i].k];
            }
            q[i].k/=g[q[i].k];
        }
        for(int j=1;j<=block;++j){
            bool flag=1;
            for(int p=1;p<=al;++p){
                if(j%sp[p]==0){
                    flag=0;
                    break;
                }
            }
            ans[q[i].x]+=(flag*d[j]);
        }
        int tot=0;
        for(int j=1;j<=top;++j){
            if(c[sta[j]]>block){
                stp[++tot]=sta[j];
                bool flag=1;
                for(int p=1;p<=al;++p){
                    if(c[sta[j]]%sp[p]==0){
                        flag=0;
                        break;
                    }
                }
            ans[q[i].x]+=flag;
            }else{
                vis[sta[j]]=0;
            }
        }
        top=tot;
        for(int j=1;j<=tot;++j){
            sta[j]=stp[j];
        }
    }
    for(int i=1;i<=m;++i){
        printf("%d\n",ans[i]);
    }
    return 0;
}

顺便附带乱搞卡常后，113ms版本[强迫症患者表示很难受，跪求大佬帮忙卡下100ms]：

#pragma GCC optimize(3,"inline","Ofast")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
const int N=50001;
int a[N],b[N],c[N],d[N],ans[N];
int e,block,top,cnt;
int sta[2][N],g[N],zhi[N];
int sp[N],al,vnow;
bool vis[N];int vit[N];
inline void read(int &ss){
    char ch=getchar();int w=0;ss=0;
    while(ch<'0'||ch>'9')w|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')ss=(ss*10+(ch-'0')),ch=getchar();
    ss=(w?-ss:ss);
}
inline void write(int x){
    if(x>9)write(x/10);
    putchar(char(x%10+'0'));
}
struct Que{
    int l,r,k,x;
}q[N];
inline bool kkk(Que x,Que y){
    return b[x.l]!=b[y.l]?b[x.l]<b[y.l]:((b[x.l]&1)?b[x.r]<b[y.r]:b[x.r]>b[y.r]);
}
inline void sai(){
    for(int i=2;i<N;++i){
        if(!g[i]){
            g[i]=i;
            zhi[++cnt]=i;
        }
        for(int j=1;j<=cnt;++j){
            if(i*zhi[j]>=N){
                break;
            }
            g[i*zhi[j]]=zhi[j];
            if(i%zhi[j]==0){
                break;
            }
        }
    }
}
int main(){
    sai();
    int n,m;
    read(n),read(m);
    block=sqrt(n+m);
    for(int i=1;i<=n;++i){
        b[i]=(i-1)/block+1;read(a[i]);
    }
    for(int i=1;i<=m;++i){
        read(q[i].l),read(q[i].r),read(q[i].k);
        q[i].x=i;
    }
    sort(q+1,q+m+1,kkk);
    int L=q[1].l,R=q[1].r;
    for(int i=L;i<=R;++i){
        --d[c[a[i]]];
        ++c[a[i]];
        ++d[c[a[i]]];
        if(c[a[i]]==block+1){
            if(!vis[a[i]]){
                vis[a[i]]=1;sta[vnow][++top]=a[i];
            }
        }
    }
    for(int i=1;i<=n;++i){ 
        if(__gcd(q[1].k,i)==1){
            ans[q[1].x]+=d[i];
        }
    }
    for(int i=2;i<=m;++i){
        vnow^=1;
        while(L>q[i].l){
            --L;--d[c[a[L]]];++c[a[L]];++d[c[a[L]]];
            if(c[a[L]]==block+1){
                if(!vis[a[L]]){
                    vis[a[L]]=1;sta[vnow][++top]=a[L];
                }
            }
        }
        while(R<q[i].r){
            ++R;--d[c[a[R]]];++c[a[R]];++d[c[a[R]]];
            if(c[a[R]]==block+1){
                if(!vis[a[R]]){
                    vis[a[R]]=1;sta[vnow][++top]=a[R];
                }
            }
        }
        while(L<q[i].l){
            --d[c[a[L]]];--c[a[L]];++d[c[a[L]]];++L;
        }
        while(R>q[i].r){
            --d[c[a[R]]];--c[a[R]];++d[c[a[R]]];--R;
        }
        al=0;
        while(g[q[i].k]){
            if(vit[g[q[i].k]]!=i){
                vit[g[q[i].k]]=i,sp[++al]=g[q[i].k];
            }
            q[i].k/=g[q[i].k];
        }
        for(int j=1;j<=block;++j){
            if(!d[j])continue;
            bool flag=1;
            for(int p=1;p<=al;++p){
                if(j%sp[p]==0){
                    flag=0;
                    break;
                }
            }
            ans[q[i].x]+=(flag*d[j]);
        }
        int tot=0;
        for(int j=1;j<=top;++j){
            if(c[sta[vnow][j]]>block){
                sta[vnow^1][++tot]=sta[vnow][j];
                bool flag=1;
                for(int p=1;p<=al;++p){
                    if(c[sta[vnow][j]]%sp[p]==0){
                        flag=0;
                        break;
                    }
                }
            ans[q[i].x]+=flag;
            }else{
                vis[sta[vnow][j]]=0;
            }
        }
        top=tot;
    }
    for(int i=1;i<=m;++i){
        write(ans[i]),putchar('\n');
    }
    return 0;
}

数列互质 题解

数列互质题解