[Ynoi2015] 此时此刻的光辉

题传

做完 CF1422F 再做这道题就肥肠有感觉了。

如果你不想再看一题那么我就无耻推销一下 我的题解。

/[/text{————————我是分割线————————}
/]

请确保你已经知道了 CF1422F 的做法。

简化题意：多次询问，求 /(/sigma_0 (/prod_{i=l}^r a_i)/)。

我会积性函数线性筛

设素数集 /(P=/{p_1, p_2, /dots p_m /}/)，则序列中的数 /(a_i/) 可表示成：

/[/prod_{j=1}^m p_j^{c_{i, j}}
/]

那么根据约数的定义（选出质因子的组合），有：

/[/sigma_0 (/prod_{i=l}^r a_i)=/prod_{j=1}^{m} (1+/sum_{i=l}^{r} c_{i, j})
/]

现在目标非常明确：维护上面这一坨东西！

由于增减一个数会在很多个括号里产生改动，所以显然不能用线段树等在线数据结构乱搞了，考虑离线下来莫队。

设 /(cnt_j =/sum_{i=l}^r c_{i, j}/)

显然不能每次移动一个数修改所有质因子的 /(cnt/)，这时候你想到了 CF1422F 的做法，根号分治，/(/sqrt{Max_a}/approx 31623=R/)。

• 对于 /(/le R/) 的素数，前缀和记下 /(a_i/) 的 /(c/)，询问的时候，暴力枚举这些数，把贡献算上（注意这里的“询问”指的不是在莫队里面搞，而是直接做）

• 对于 /(/ge R/) 的素数，只有一个，所以直接上莫队，每次直接对应修改这个数。

然后打个表，发现 /(/le R/) 的素数有 /(3000/) 多个，空间飞天，怎么办？

考虑到这题对阈值上部分的要求没那么紧（不像 CF1422F 那样要求区间不同种类数且指数为 /(1/)），也就是说，我们在莫队的时候多处理几个素数是没问题的，所以我们珂以适当地调低阈值，这里选择 /(R=p_{239}=1499/)，然后就珂以愉快地跑过去了。

复杂度大概是 /(O(239(n+q) + k n /sqrt q)/)，/(k/) 是一个小常数，不超过 /(3/)（因为 /(3/) 个 /(10^3/) 乘起来就爆值域了）。

注意大质因子要离散化，这里使用 map。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair <int, int> PI;
inline int read(){
    char ch=getchar();int x=0, f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
const int mo=19260817;
inline int ksm(int a, int b){
    int ret=1;for(; b; b>>=1, a=1ll*a*a%mo)
    if(b&1) ret=1ll*ret*a%mo;
    return ret;
}
const int N=1e5+1;
const int R=31623;//sqrt(1000000000)
int tot, Su[3402], u[R];//prime=3401;
int sum[N][240], a[N], n, m, Mx, up;
int newcnt;
map <int, int> Mp;
vector <PI> pri[N];
int Getc(int &x, int p){
    if(x%p) return 0;int res=0;
    while(!(x%p)) res++, x/=p;
    return res;
}
void Reverse(int id){//分解 
    int S=a[id];
    for(int i=up+1; i<=tot; i++)
        if(S%Su[i]==0){
            int x=Getc(S, Su[i]);
            pri[id].push_back(PI(i, x));
        }
    if(S>1){
    	if(!Mp[S]) ++newcnt, Mp[S]=newcnt+tot;
        pri[id].push_back(PI(Mp[S], 1));
    }
}
void pre(int E){
    for(int i=2; i<=R; i++){
        if(!u[i]) Su[++tot]=i;
        for(int j=1; j<=tot&&i*Su[j]<=R; j++){
            u[i*Su[j]]=1;if(!(i%Su[j])) break;
        }
        if(i<=E) up=tot;
    }
    up=min(239, up);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=up; j++)
            sum[i][j]=sum[i-1][j]+Getc(a[i], Su[j]);
}
int dis, ans[N];
struct Query{
    int x, y, id;
    bool operator < (const Query &S) const{
        if(x/dis!=S.x/dis) return x/dis<S.x/dis;
        return y<S.y;
    }
    void get(int s){x=read(), y=read(), id=s;}
}Q[N];
int inv[N], now=1, cnt[3402+N];
inline void add(int x){//乘上 a[x]
    for(int i=0; i<pri[x].size(); i++){
        PI tmp=pri[x][i];int las=cnt[tmp.first];
        now=1ll*now*inv[las]%mo*(las+tmp.second)%mo;
        cnt[tmp.first]+=tmp.second;
    }
}
inline void del(int x){//除掉 a[x]
    for(int i=0; i<pri[x].size(); i++){
        PI tmp=pri[x][i];int las=cnt[tmp.first];
        now=1ll*now*inv[las]%mo*(las-tmp.second)%mo;
        cnt[tmp.first]-=tmp.second;
    }
}
inline void move(int &l, int &r, int x, int y){
    while(l>x) add(--l);
    while(r<y) add(++r);
    while(r>y) del(r--);
    while(l<x) del(l++);
    return ;
}
signed main(){
    n=read(), m=read();if(!m) return 0;dis=n/sqrt(m);
    for(int i=1; i<=n; i++) Mx=max(Mx, a[i]=read());
    inv[0]=1;for(int i=1; i<N; i++) inv[i]=ksm(i, mo-2);//计算逆元 
    pre(sqrt(Mx));
    for(int i=1; i<=n; i++) Reverse(i);//将 a[i] 中大于 su[239] 的全部丢到一起
    for(int i=1; i<=m; i++){
        ans[i]=1;Q[i].get(i);
        for(int j=1; j<=up; j++)
            ans[i]=1ll*ans[i]*(sum[Q[i].y][j]-sum[Q[i].x-1][j]+1)%mo;//根号分治，先计算小素数的贡献 
    }
    for(int i=1; i<=tot+newcnt; i++) cnt[i]=1;
    sort(Q+1, Q+m+1);int L=1, R=0;
    for(int i=1; i<=m; i++){
        move(L, R, Q[i].x, Q[i].y);
        ans[Q[i].id]=1ll*ans[Q[i].id]*now%mo;
    }
    for(int i=1; i<=m; i++) printf("%d/n", (ans[i]%mo+mo)%mo);
    return 0;
}

常数肥肠大.jpg