好数
时间限制: 1000 ms 内存限制: 131072 KB
提交数: 50 通过数: 15
【题目描述】
我们将满足下列条件的数称为好数。
1. 是0或1
2. 这个数所有比它小的和它互质的数能排成等差数列。例如8，比8小且和8互质的数有1,3,5,7，正好排成等差数列。
现在给你n个数，一共三种操作
1. 询问区间[L,R]间有多少个好数
2. 将区间[L,R]内所有数对x取模
3. 将第k个数修改为c
【输入】
第一行包含两个正整数n,m，表示序列长度和操作个数
第二行包含n个整数Ai，表示这个序列
接下来m行，每行表示一个操作
1 L R 表示第一类操作
2 L R x表示第二类操作
3 k c表示第三类操作
【输出】
对于每个第一类操作输出一行一个数表示答案
【输入样例】
3 6 4 6 9 1 1 3 1 3 3 2 1 1 10 1 1 3 3 2 4 1 1 3
【输出样例】
2 0 2 2
【提示】
【样例输入2】
8 5
12 24 17 31 16 21 18 30
1 2 5
2 4 7 7
3 2 13
1 1 8
1 3 6
【样例输出2】
3
6
4
对于20%的数据N,M<=100,数值<=100
对于另20%的数据N,M<=1000
对于另30%的数据，没有第二类操作
对于100%的数据N,M<=100000,数值<=1000000
题解：
显然，好数除6以外，其余数都是2n或素数
预处理出所有好数，然后套一颗线段树，维护区间好数个数与区间最大值
在成功取模的情况下，原数至少会减小一半，故一个数最多只能被成功取模log（n）次
所以对于每次取模操作，判断当前节点最大值是否小于模数，是的话就直接return，否则就直接暴力递归到叶子修改即可
#include<bits/stdc++.h> using namespace std; struct tree{ int l,r,sum,mx; }node[100005<<2]; int n,m,cnt=0; bool mark[1000005]; int arr[100005],p[1000005]; inline int read() { int X=0,w=0; char ch=0; while(!isdigit(ch)) {w|=ch=='-';ch=getchar();} while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } inline int maxn(int a,int b) { return a>b?a:b; } inline void get_prime() { for(register int i=2;i<=1000005;i++) { if(mark[i]) p[++cnt]=i; for(register int j=1;j<=cnt&&i*p[j]<=1000005;j++) { mark[i*p[j]]=false; if(i%p[j]==0) break; } } } inline void get_else() { int r=4; while(r<1000005) { mark[r]=true; r=r<<1; } for(register int i=0;i<=8;i++) mark[i]=true; } inline void build(int k,int ll,int rr) { node[k].l=ll;node[k].r=rr; if(ll==rr) { if(mark[arr[ll]]) node[k].sum=1; else node[k].sum=0; node[k].mx=arr[ll]; return; } int mid=(ll+rr)>>1; build(2*k,ll,mid); build(2*k+1,mid+1,rr); node[k].mx=maxn(node[2*k].mx,node[2*k+1].mx); node[k].sum=node[2*k].sum+node[2*k+1].sum; } inline void modify(int k,int p,int o,int val) { if(node[k].l==node[k].r&&node[k].l==p) { node[k].sum=o; node[k].mx=val; return; } int mid=(node[k].l+node[k].r)>>1; if(p<=mid) modify(2*k,p,o,val); if(mid<p) modify(2*k+1,p,o,val); node[k].sum=node[2*k].sum+node[2*k+1].sum; node[k].mx=maxn(node[2*k].mx,node[2*k+1].mx); } inline int query(int k,int ll,int rr) { int ret=0; if(ll<=node[k].l&&node[k].r<=rr) return node[k].sum; int mid=(node[k].l+node[k].r)>>1; if(ll<=mid) ret+=query(2*k,ll,rr); if(mid<rr) ret+=query(2*k+1,ll,rr); return ret; } inline void modd(int k,int ll,int rr,int md) { if(node[k].mx<md) return; if(node[k].l==node[k].r) { node[k].mx=node[k].mx%md; if(mark[node[k].mx]) node[k].sum=1; else node[k].sum=0; return; } int mid=(node[k].l+node[k].r)>>1; if(ll<=mid) modd(2*k,ll,rr,md); if(mid<rr) modd(2*k+1,ll,rr,md); node[k].sum=node[2*k].sum+node[2*k+1].sum; node[k].mx=maxn(node[2*k].mx,node[2*k+1].mx); } int main() { memset(mark,true,sizeof(mark)); n=read();m=read(); for(register int i=1;i<=n;i++) arr[i]=read(); get_prime(); get_else(); build(1,1,n); for(register int i=1;i<=m;i++) { int opt; opt=read(); if(opt==1) { int a,b; a=read();b=read(); printf("%d ",query(1,a,b)); } if(opt==2) { int a,b,x; a=read();b=read();x=read(); modd(1,a,b,x); } if(opt==3) { int e,c,g; e=read();c=read(); if(mark[c]) g=1; else g=0; modify(1,e,g,c); } } return 0; }