Steven_Meng's Blog

传送门

首先，附送本题数据生成器：

#include <bits/stdc++.h>
using namespace std;
inline int gen(){
    return (rand()<<15)|(rand());
}
int main(){
    srand(time(NULL));
    freopen("yukideru.in","w",stdout);
    int n=100000,m=100000;
    printf("%d %d\n",n,m);
    for (register int i=1;i<=n;++i){
        printf("%d ",gen()%1000000000);
    }
    printf("\n");
    for (register int i=1;i<=m;++i){
        int l=gen()%n+1,r=gen()%n+1;
        if (l>r) swap(l,r);
        printf("%d %d\n",l,r);
    }
}

$Pro$

珂朵莉给你了一个长为$n$的序列，有$m$次查询，每次查询一段区间的乘积的约数个数$\mod 19260817$的值

$n,m\le 100000$
$1 \le a_i \le 1000000000$

$Sol$

首先，根据小学奥数（雾），设$D(x)$为$x$的约数个数，设$x=\prod p_i^{k_i} (p_i \in \text{prime})$，我们有

$D(x)=\prod (k_i+1)$。

于是，每次莫队转移的时候，我们把新加进的那个数（设为$A$）分解质因数，假设现在分解出了一个质数$p$，那么答案$\times inv(cnt[p]+1)$，然后$cnt[p]++$，最后$\times (cnt[p]+1)$，但是这样肯定会炸掉，因为质因数很多，考虑到$A$的质因数很多都是$<1000$，根据其他题解中的说法：$A$最多也只有两个$>1000$的质因数。

所以，方法就有了，考虑把$<1000$的和$\geq 1000$的质数分开考虑，因为$<1000$的质数只有$169$个，所以每次重新算也没有关系，$\geq 1000$的质数就按照上面方法维护就可以了。

再看怎么具体实现，首先预处理逆元和线性筛质数都是必须的

$1.$考虑维护$<1000$的质数对答案的贡献，维护一个前缀和数组$sum$，其中$sum[i][p]$代表$\prod_{j=1}^{i} a_j$中$p$出现的次数，求$\prod_{j=l}^{r} a_j$中$p$出现的次数，就是前缀和做一下差，即$sum[r][p]-sum[l-1][p]$。

$2.$考虑维护$\geq 1000$的质数对答案的贡献，由于$\geq1000$的质数比较多，不好记录，又发现其实答案只和$k_i$有关，和$p_i$是没关的，所以只要统计不同的数的个数即可，我们这里用一种比较偷懒的办法，新来一个数，我们把它扔进一个$map$里面，如果他出现过，那么记录他在$map$里面的编号，否则新建一个编号，这样就起到去重和离散化的效果（这种办法太偷懒了，导致程序效率不高），最后像上面说的一样，莫队维护一下。

注意：中间量要开$\text{long long}$，使劲卡常，此代码多交几次或许能$\rm AC$

时间复杂度$O(n \sqrt{n}*169)$

总结一下，质数在一段区间的稠密度是不同的，标程就是根据这个性质，分布稠密的小范围暴力搞，分布稀疏的大范围莫队搞，这是一种重要的思想。

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define MOD 19260817
#define MAXN 200005
#define MAXP 32005
#define CNT 169 //小于1000的质数个数
#define ll long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
//思路：把<1000的和>=1000的分开考虑
static int inv[MAXN];
static int nprime[MAXN];
static int cnt,prime[MAXN],pos[MAXN];//预处理逆元，筛质数，初始化莫队
inline int ksm(int b,int k){
    int ans=1;
    while (k){
        if (k&1) ans=((long long)ans*(long long)b)%MOD;
        b=((long long)b*(long long)b)%MOD;
        k>>=1;
    }
    return ans;
}
inline void Init(int n){
    for (register int i=0;i<MAXN;++i){
        inv[i]=ksm(i,MOD-2)%MOD;
    }

    for (register int i=2;i<MAXP;++i){
        if (!nprime[i]){
            for (register int j=i*2;j<MAXP;j+=i){
                nprime[j]=true;
            }
        }
    }
    for (register int i=2;i<MAXP;++i){
        if (!nprime[i]) prime[++cnt]=i;
    }

    int Size=sqrt(n);
    for (register int i=1;i<=n;++i){
        pos[i]=(i-1)/Size+1;
    }
}

static int sum[MAXN][CNT];
static int v[MAXN][CNT],top[MAXN];
static map<int,int>M;//暂时没有想到好的方法替代这个Map
inline void AddV(int i,int val){
    if (M.count(val)==0) v[i][++top[i]]=M[val]=M.size()+1;//新建一个编号
    else v[i][++top[i]]=M[val];//沿用原来的编号
}

struct Query{
    int l,r,id;
}q[MAXN];
inline bool operator < (const Query &A,const Query &B){
    return pos[A.l]<pos[B.l]||(pos[A.l]==pos[B.l]&&((pos[A.l]&1)?A.r<B.r:A.r>B.r));
}
int ans;
static int c[MAXN];
inline void Add(int x){
    for (register int i=1;i<=top[x];++i){
        ans=((long long)ans*inv[c[v[x][i]]+1])%MOD;
        ++c[v[x][i]],c[v[x][i]]%=MOD;
        ans=((long long)ans*(c[v[x][i]]+1))%MOD;
    }
}
inline void Del(int x){
    for (register int i=1;i<=top[x];++i){
        ans=((long long)ans*(inv[c[v[x][i]]+1]))%MOD;
        --c[v[x][i]],(c[v[x][i]]+=MOD)%=MOD;
        ans=((long long)ans*(c[v[x][i]]+1))%MOD;
    }
}
static int Ans[MAXN];
int main(){
    // freopen("yukideru.in","r",stdin);
    // freopen("yukideru.out","w",stdout);
    int n=read(),m=read();
    Init(n);
    for (register int i=1;i<=n;++i){
        int a=read();
        for (register int j=1;j<CNT;++j){//分开搞
            sum[i][j]=sum[i-1][j];
            while (a%prime[j]==0){
                a/=prime[j],++sum[i][j];
            }
        }
        if (a==1) continue;
        for (register int j=CNT;j<=cnt;++j){
            if (a==1) break;
            while (a%prime[j]==0){
                a/=prime[j],AddV(i,prime[j]);
            }
        }
        if (a!=1) AddV(i,a);
    }
    for (register int i=1;i<=m;++i){
        int l=read(),r=read();
        q[i].l=l,q[i].r=r,q[i].id=i;
    }
    sort(q+1,q+1+m);
    register int l=1,r=0;
    ans=1ll;
    for (register int i=1;i<=m;++i){
        while (l>q[i].l) Add(--l);
        while (r<q[i].r) Add(++r);
        while (l<q[i].l) Del(l++);
        while (r>q[i].r) Del(r--);
        Ans[q[i].id]=ans;
        for (register int j=1;j<CNT;++j){
            Ans[q[i].id]=((long long)Ans[q[i].id]*(sum[r][j]-sum[l-1][j]+1))%MOD;//前缀和搞一下
        }
    }
    for (register int i=1;i<=m;++i){
        printf("%d\n",Ans[i]);
    }
}