数据结构|20200502省选模拟赛 C （莫队+数值分治）
【数据结构|20200502省选模拟赛 C （莫队+数值分治）】
文章图片
题解 或许这就是人生吧
这题似乎比[Ynoi2015]此时此刻的光辉更毒瘤
一些数的子集的gcd很难直接计算
我们就来考虑每种质因子的贡献
则答案就是
文章图片
f[p^k]表示在这段数中有多少个子集的gcd被p^k整除
显然f[p^k]=2^g[p^k]-1，g[p^k]表示这段区间中有多少个数被p^k整除
稍微变换一下形式
文章图片
文章图片
文章图片
最后的这个形式就比较简单
我们如果直接用莫队，时间复杂度将会是O(n*sqrt(m)*(sqrt(w)/ln(w))*logw+m)（有一个枚举质因子以及其幂次k复杂度和一个快速幂复杂度）
最后的那个logw可以通过预处理来消掉
至于sqrt(w)/ln(w)
我们可以对数值进行分治
把<=sqrt(w)的质数单独拿出来，把它们的可能的所有幂次求出来，做一个前缀和
就可以把这一部分的复杂度分一点到后面的O(m)
>sqrt(w)的质数由于每个数只有一个，所以可以O(1)加入
所以复杂度就平衡为O(n*sqrt(m)+m*2sqrt(sqrt(w))/ln(w))
代码：（细节超多）（vector要reverse否则会爆内存）
#include
#include
#include
#include
using namespace std;
inline int gi()
{
char c;
int num=0,flg=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
while(c>='0'&&c<='9'){num=num*10+c-48;
c=getchar();
}
return num*flg;
}
#define N 100005
#define D 331
const int mod=998244353;
int n,m,a[N];
int prime[N],tot;
bool vis[N];
int num[N];
int sum[180][N],pr[180],scnt;
//prework: calculate the pw and inv of prime>=sqrt(n)
int tong[N];
vector pw[N],inv[N];
int ksm(int x,int y)
{
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%mod;
y>>=1;
x=1ll*x*x%mod;
}
return ret;
}
void shai()
{
int i,j,k;
vis[1]=1;
for(i=2;
i<=100000;
i++){
if(!vis[i])prime[++tot]=i;
for(j=1;
j<=tot;
j++){
int tmp=i*prime[j];
if(tmp>100000)break;
vis[tmp]=1;
if(i%prime[j]==0)break;
}
}
for(i=1;
i<=tot;
i++){
int x=prime[i];
if(x<=D){
for(j=x;
j<=100000;
j*=x){
pr[++scnt]=x;
for(k=1;
k<=n;
k++){
sum[scnt][k]=sum[scnt][k-1];
if(a[k]%j==0)sum[scnt][k]++;
}
if(j==x){
pw[x].reserve(sum[scnt][n]+1);
pw[x].push_back(x);
for(k=1;
k<=sum[scnt][n];
k++)
pw[x].push_back(1ll*pw[x][k-1]*pw[x][k-1]%mod);
for(k=1;
k<=sum[scnt][n];
k++)
pw[x][k]=1ll*pw[x][k]*pw[x][k-1]%mod;
}
}
}
}
for(i=1;
i<=n;
i++){
for(j=1;
j<=tot;
j++){
if(prime[j]>D)break;
while(a[i]%prime[j]==0)
a[i]/=prime[j];
}
tong[a[i]]++;
}
for(i=1;
i<=100000;
i++){
int x=i;
if(tong[x]){
pw[x].reserve(tong[x]+1);
inv[x].reserve(tong[x]+1);
pw[x].push_back(x);
inv[x].push_back(ksm(x,mod-2));
for(j=1;
j<=tong[x];
j++){
pw[x].push_back(1ll*pw[x][j-1]*pw[x][j-1]%mod);
inv[x].push_back(1ll*inv[x][j-1]*inv[x][j-1]%mod);
}
}
}
}
int bel[N];
struct node{
int l,r,id;
bool operator < (const node &t)const{
int f=bel[l];
return ft.r)));
}
}q[N];
int cnt[N],ans,mul;
void add(int x)
{
if(x==1)return;
ans=1ll*ans*pw[x][cnt[x]]%mod;
cnt[x]++;
}
void del(int x)
{
if(x==1)return;
cnt[x]--;
ans=1ll*ans*inv[x][cnt[x]]%mod;
}
int lan[N];
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
int i,j,l,r;
n=gi();
m=gi();
for(i=1;
i<=n;
i++){a[i]=gi();
bel[i]=(i-1)/D+1;
}
for(i=1;
i<=m;
i++){q[i].l=gi();
q[i].r=gi();
q[i].id=i;
}
sort(q+1,q+m+1);
shai();
ans=mul=1;
l=q[1].l;
r=q[1].r;
for(i=q[1].l;
i<=q[1].r;
i++)add(a[i]);
for(i=1;
i<=scnt;
i++)
if(sum[i][r]-sum[i][l-1]>0)
mul=1ll*mul*pw[pr[i]][sum[i][r]-sum[i][l-1]-1]%mod;
lan[q[1].id]=1ll*ans*mul%mod;
for(i=2;
i<=m;
i++){
while(rq[i].l)l--,add(a[l]);
while(r>q[i].r)del(a[r]),r--;
while(l0)
mul=1ll*mul*pw[pr[j]][sum[j][r]-sum[j][l-1]-1]%mod;
lan[q[i].id]=1ll*ans*mul%mod;
}
for(i=1;
i<=m;
i++)
printf("%d\n",lan[i]);
} 推荐阅读
- 日省11
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- 《数据结构与算法之美》——队列
- 文学女神的天空(诗歌原创)??云南省文山州文山市:沈小宁
- 静生慧，行生风！
- 对工作的反省
- 成铁检
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 内省(20)
- 山东省的考生一定要看！专业技术人员资格考试考生疫情防控告知书！