鬼知道我加了多少优化操作卡过去的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,P=19260817;
bool v[N+10];int p[N],pr,inv[N*16];map<int,int>mp;
void init()
{
	pr=0;memset(v,0,sizeof(v));
	for(int i=2;i<=N/2;i++)
	{
		if(!v[i])p[++pr]=i,mp[i]=pr;
		for(int j=1;(j<=pr)&&(i*p[j]<=N/2);j++)
		{
			v[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
	inv[1]=1;
	for(int i=2;i<=(N-10)*16;i++)
		inv[i]=(P-P/i)*inv[P%i]%P;
}
int cnt[N],sum,B,a[N],len;
int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;}
struct node{int x,y;};vector<node>G[N];
struct node1{int l,r,id;}q[N];int ans[N];
bool cmp(node1 n1,node1 n2){return n1.l/B!=n2.l/B?n1.l<n2.l:(n1.l/B)&1?n1.r<n2.r:n1.r>n2.r;}
void add(int x)
{
	for(auto i:G[x])
	{
		sum=sum*inv[cnt[i.x]+1]%P;
		cnt[i.x]+=i.y;
		sum=sum*(cnt[i.x]+1)%P;
	}
}
void del(int x)
{
	for(auto i:G[x])
	{
		sum=sum*inv[cnt[i.x]+1]%P;
		cnt[i.x]-=i.y;
		sum=sum*(cnt[i.x]+1)%P;
	}
}
signed main()
{
	init();sum=1;len=pr;
	int n,m;cin>>n>>m;B=n/sqrt(m);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];int x=a[i];
		for(int j=1;j<=pr&&x!=1&&p[j]*p[j]<=x;j++)if(x%p[j]==0)
		{
			int s1=0;
			while(x%p[j]==0)x/=p[j],s1++;
			G[i].push_back({mp[p[j]],s1});
		}
		if(x!=1)
		{
			if(!mp[x])mp[x]=++len;
			G[i].push_back({mp[x],1});
		}
	}
	for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].id=i;
	sort(q+1,q+m+1,cmp);
	for(int i=1,l=1,r=0;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]=sum;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩

我永远喜欢珂朵莉。

$10^9$以内的数最多有10个不同的质因子。

考虑对其质因数分解。

由于值域范围过大，考虑使用Pollard-Rho算法。

这里普通的Pollard-Rho算法可能会TLE。如果你的代码能通过模板题，那基本上没问题（窝反正直接把以前写的板子拉过来然后调了调参）。

之后，你就会得到最多$10n$个不同的质因数。对其进行离散化，开桶记录。

然后上莫队，对于每次指针的偏移，把它所有的质因数加到桶里，同时维护约数个数即可。

这部分时间复杂度$O(10n\sqrt n)$，加上上面的质因数分解的玄学期望复杂度，只能获得82分的好成绩。

我们考虑把每个数$1000$以内的质因子先取出来（$1000$以内共168个质数），然后，对其做前缀和，记录前缀的出现次数。

然后，由于$1001^3>10^9$，所以每个数剩下最多不超过2个质因子。这部分用Pollard_Rho找即可。

然后莫队的时候，对于前面168个质数就可以不用维护，直接用前缀和。

而对于后面的大质因子，再离散化处理即可。由于每个数最多两个质因子，所以常数就小了很多。

而由于筛掉了很多小的质因子，Pollard_Rho的速度也会变快。然后就足以通过此题。

Code：

#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstring>
#define ctz __builtin_ctz
using namespace std;
#ifdef ONLINE_JUDGE
struct istream{
    char buf[23333333],*s;
    inline istream(){
        buf[fread(s=buf,1,23333330,stdin)]='\n';
        fclose(stdin);
    }
    inline istream&operator>>(int&d){
        d=0;
        for(;!isdigit(*s);++s);
        while(isdigit(*s))
        d=(d<<3)+(d<<1)+(*s++^'0');
        return*this;
    }
}cin;
struct ostream{
    char buf[8000005],*s;
    inline ostream(){s=buf;}
    inline ostream&operator<<(int d){
        if(!d){
            *s++='0';
        }else{
            static int w;
            for(w=1;w<=d;w*=10);
            for(;w/=10;d%=w)*s++=d/w^'0';
        }
        return*this;
    }
    inline ostream&operator<<(const char&c){*s++=c;return*this;}
    inline void flush(){
        fwrite(buf,1,s-buf,stdout);
        s=buf;
    }
    inline~ostream(){flush();}
}cout;
#else
#include<iostream>
#endif
int pri[170],cct=0,sum[100005][169],num[1005];
void sieve(){
    for(int i=2;i<=1000;++i)num[i]=1;
    for(int i=2;i<=1000;++i)
    if(num[i]){
        pri[num[i]=++cct]=i;
        for(int j=i<<1;j<=1000;j+=i)num[j]=0;
    }
}
using LoveLive=long long;
vector<int>tj;
const int pr[]={2,3,5,7,11,13,17};
int gcd(int a,int b){
    if(!a||!b)return a|b;
    int t=ctz(a|b);
    a>>=ctz(a);
    do{
        b>>=ctz(b);
        if(a>b)swap(a,b);
        b-=a;
    }while(b);
    return a<<t;
}
inline int power(int a,int b,const int&md){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=(LoveLive)ans*a%md;
        a=(LoveLive)a*a%md;
    }
    return ans;
}
int miller_rabin(int p){
    if(p==2)return 1;
    int b=p-1;
    int t=0;
    while(!(b&1))b>>=1,++t;
    for(int i:pr){
        int r=power(i%(p-2)+2,b,p);
        if(r==1||r==p-1)continue;
        int ok=1;
        for(int j=1;j<=t&&ok;++j){
            r=(LoveLive)r*r%p;
            if(r==p-1)ok=0;
        }
        if(ok)return 0;
    }
    return 1;
}
void pollard_rho(int&n,int c){
    int k=2,x=rand()%(n-1)+1,y=x,q=1,t=1;
    for(;;k<<=1,y=x,q=1){
        for(int i=1;i<=k;++i){
            x=((LoveLive)x*x%n+c)%n;
            q=(LoveLive)q*abs(x-y)%n;
            if(!(i&63)){
                t=gcd(q,n);
                if(t>1)break;
            }
        }
        if(t>1||(t=gcd(q,n))>1)break;
    }
    n=t;
}
void find(int n,int c){
    if(n==1)return;
    if(miller_rabin(n)){tj.push_back(n);return;}
    int p=n;
    while(p>=n)pollard_rho(p,c--);
    n/=p;
    tj.push_back(n),tj.push_back(p);
}
#define N 100005
const int md=19260817;
int n,m,a[N],inv[N*3],cnt[N],tot[N*2],now=1,ans[N];
int p[N][3];
vector<int>lr;
struct que{
    static const int siz=317;
    int l,r,id;
    inline bool operator<(const que&rhs)const{
        return((l/siz!=rhs.l/siz)?(l<rhs.l):r<rhs.r);
    }
}q[N];
inline void add(int id){
    for(register int i=1;i<=cnt[id];++i)
    now=(LoveLive)now*inv[tot[p[id][i]]]%md*(tot[p[id][i]]+1)%md,++tot[p[id][i]];
}
inline void del(int id){
    for(register int i=1;i<=cnt[id];++i)
    now=(LoveLive)now*inv[tot[p[id][i]]]%md*(tot[p[id][i]]-1)%md,--tot[p[id][i]];
}
int main(){
    srand(19260817);
    sieve();
    cin>>n>>m;
    inv[1]=1;
    for(int i=2;i<=3*n;++i)inv[i]=(md-md/i)*1LL*inv[md%i]%md;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        memcpy(sum[i],sum[i-1],sizeof*sum);
        for(int j=1;j<=cct&&pri[j]*pri[j]<=a[i];++j)
        while(!(a[i]%pri[j])){
            ++sum[i][j];
            a[i]/=pri[j];
        }
        if(a[i]>1){
            if(a[i]<=pri[cct]){
                ++sum[i][num[a[i]]];
                continue;
            }
            tj.clear();
            find(a[i],23333);
            for(int it:tj)
            p[i][++cnt[i]]=it,lr.push_back(it);
        }
    }
    sort(lr.begin(),lr.end());
    lr.erase(unique(lr.begin(),lr.end()),lr.end());
    for(int i=1;i<=n;++i)
    for(int j=1;j<=cnt[i];++j)p[i][j]=lower_bound(lr.begin(),lr.end(),p[i][j])-lr.begin();
    for(int i=1;i<=m;++i)cin>>q[q[i].id=i].l>>q[i].r;
    sort(q+1,q+m+1);
    for(int i=0;i<n<<1;++i)tot[i]=1;
    for(int i=1,l=1,r=0;i<=m;++i){
        while(r<q[i].r)add(++r);
        while(r>q[i].r)del(r--);
        while(l>q[i].l)add(--l);
        while(l<q[i].l)del(l++);
        int&out=ans[q[i].id];out=now;
        for(int j=1;j<=cct;++j)
        out=(LoveLive)out*(sum[r][j]-sum[l-1][j]+1)%md;
    }
    for(int i=1;i<=m;++i)
    cout<<ans[i]<<'\n';
    return 0;
}