NC222294. 数学家的迷题
描述
伟大的数学家费牛于自己的家中过世，桌上的纸笔记录着他生前研究的最后一个问题。
这个问题是这样的，首先给出个数字，第
个数字为
。接下来进行
次操作，每次操作的类型如下：
1：将的值改为
。
2：令，求
能被多少个不同的素数整除。
这种问题自然是难不倒费牛，可是他在草稿纸上写着：“我已经想到了一个绝妙的方法，可惜这儿空白太小写不下”。
没办法，现在只能请你代替费牛回答每个类型问题的答案。
输入描述
第一行两个正整数
,
，其中
,
。
第二行
，
。
接下来
表示操作类型，
。
若
，输入正整数
与
，其中
,
。
若
，输入正整数
与
，其中
。
输出描述
输出每个
示例1
输入:
5 3 2 3 6 6 6 2 1 4 1 4 5 2 1 4
输出:
2 3
C++ 解法, 执行用时: 424ms, 内存消耗: 154696K, 提交时间: 2021-06-25 22:01:39
#include<bits/stdc++.h>
using namespace std;
bitset<9600>s,S[200005];
int L=0,T[9600];
bool V[100005]={0};
void update(int L,int R,int pos,int rt)
{
if(L==pos&&R==pos)
{
S[rt]=s;
return;
}
int M=(L+R)>>1;
if(M>=pos)update(L,M,pos,rt<<1);
if(M<pos)update(M+1,R,pos,rt<<1|1);
S[rt]=S[rt<<1]|S[rt<<1|1];
}
void search(int L,int R,int l,int r,int rt)
{
if(l<=L&&R<=r)
{
s|=S[rt];
return;
}
int M=(L+R)>>1;
if(M>=l)search(L,M,l,r,rt<<1);
if(M<r)search(M+1,R,l,r,rt<<1|1);
}
int main()
{
int i,j,cnt,n,m,op,l,r,id,x;
for(i=2;i<=1e5;i++)
{
if(!V[i])T[L++]=i;
for(j=0;j<L&&T[j]*i<=1e5;j++)
{
V[i*T[j]]=1;
if(i%T[j]==0)break;
}
}
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&x),s.reset();
for(j=0;T[j]*T[j]<=x;j++)
{
for(cnt=0;x%T[j]==0;x/=T[j])cnt++;
if(cnt)s[j]=1;
}
if(x!=1)j=lower_bound(T,T+L,x)-T,s[j]=1;
update(1,n,i,1);
}
while(m--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d",&id,&x),s.reset();
for(j=0;T[j]*T[j]<=x;j++)
{
for(cnt=0;x%T[j]==0;x/=T[j])cnt++;
if(cnt)s[j]=1;
}
if(x)j=lower_bound(T,T+L,x)-T,s[j]=1;
update(1,n,id,1);
}
else
{
scanf("%d%d",&l,&r);
s.reset(),search(1,n,l,r,1);
printf("%d\n",s.count());
}
}
return 0;
}