题目描述
由于你不会设计哥德尔机，所以你决定先做一道数据结构题：
给定一个长度为 \(n\) 的序列 \(a_1\cdots a_n\)。你需要回答 \(m\) 个询问，第 \(i\) 个询问给定一个区间 \([l_i,r_i]\)，请你求出这个区间中所有非空子集的最大公约数的乘积。由于答案可能很大，每次询问请你求出其对 \(998244353\) 取模的结果。
提示
对于 \(100\%\) 的数据，满足 \(1\le n,m,a_i\le 10^5\)，\(1\le l_i\le r_i\le n\)。
既然是乘法，对每个质数的次幂单独考虑。
尝试用莫队去维护质数的次幂。我们现在要知道 \(p^{2^i-1}\) 的值，这个可以用倍增弄出来。
但是转移的时候需要枚举所有质因数的次幂，这个复杂度是 \(O(logn)\)，复杂度 \(O(n\sqrt nlogn)\)，过不了。
有关因数的问题，考虑根号分治。把所有质数次幂 按照质数大小分 成 \(\le 320\) 和 \(>320\) 来考虑。对于 \(\le 320\) 的质数的次幂之和不超过 \(120\)，所以拿出去用前缀和处理就行了。 每个数只有一个 \(\ge320\) 的质数，在莫队的时候 \(O(1)\) 维护就可以了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,P=998244353,iv=P+1>>1;
int n,id[N],sq,l[N],r[N],p=1,q,pr[N],ps[N],ret=1,k,pp[N],cn[N],a[N],to[N],m,ans[N],c[N],fr[N],s[N];
vector<int>g[N],h[N];
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
int cmp(int x,int y)
{
if(l[x]/sq^l[y]/sq)
return l[x]<l[y];
return r[x]<r[y];
}
int pown(int x,int y)
{
if(!y)
return 1;
int t=pown(x,y>>1);
if(y&1)
return 1LL*t*t%P*x%P;
return 1LL*t*t%P;
}
void add(int x,int y)
{
ret=1LL*ret*h[x][c[x]]%P;
c[x]+=y;
ret=1LL*ret*g[x][c[x]]%P;
}
int main()
{
n=read(),m=read();
sq=sqrt(n);
for(int i=2;i<=320;i++)
{
if(pr[i])
continue;
for(int j=i;j<=100000;j*=i)
ps[++k]=j,fr[k]=i;
for(int j=2;j*i<=100000;j++)
pr[i*j]=1;
}
for(int i=1;i<=100000;i++)
to[i]=1;
for(int i=321;i<=100000;i++)
{
if(!pr[i])
{
g[i].push_back(i);
h[i].push_back(pown(i,P-2));
for(int j=1;j*i<=100000;j++)
to[i*j]=i,pr[i*j]=1;
}
}
g[1].push_back(1);
h[1].push_back(1);
for(int i=1;i<=n;i++)
{
a[i]=read();
g[to[a[i]]].push_back(1LL*g[to[a[i]]].back()*g[to[a[i]]].back()%P);
h[to[a[i]]].push_back(1LL*h[to[a[i]]].back()*h[to[a[i]]].back()%P);
}
for(int i=1;i<=m;i++)
l[i]=read(),r[i]=read(),id[i]=i,ans[i]=1;
for(int i=1;i<=k;i++)
{
for(int j=pp[0]=1;j<=n;j++)
s[j]=a[j]%ps[i]==0;
int iv=pown(pp[0]=fr[i],P-2);
for(int j=1;j<=n;j++)
s[j]+=s[j-1],pp[j]=1LL*pp[j-1]*pp[j-1]%P;
for(int j=1;j<=m;j++)
ans[j]=1LL*ans[j]*pp[s[r[j]]-s[l[j]-1]]%P*iv%P;
}
sort(id+1,id+m+1,cmp);
for(int i=1;i<=m;i++)
{
while(p>l[id[i]])
add(to[a[--p]],1);
while(q<r[id[i]])
add(to[a[++q]],1);
while(p<l[id[i]])
add(to[a[p++]],-1);
while(q>r[id[i]])
add(to[a[q--]],-1);
ans[id[i]]=1LL*ans[id[i]]*ret%P;
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}