中文题面：
问题描述】
我们定义一个非负整数是“好数”，当且仅当它符合以下条件之一：
1. 这个数是0或1
2. 所有小于这个数且与它互质的正整数可以排成一个等差数列
例如，8就是一个好数，因为1,3,5,7排成了等差数列。
给出N个非负整数，然后进行如下三个操作：
1. 询问区间[L,R]有多少个好数
2. 将区间[L,R]内所有数对S取余(S≤1000000)
3. 将第C个数更改为X
提示：如果你不知道如何判断一个数是否为好数，你可以打个表找找规律。
【输入格式】
输入文件名为good.in。
第一行包含两个正整数N和M，M表示操作数目
第二行包含N个非负整数。
接下来的M行每行表示1个操作：“1 L R”表示第1个操作，“2 L R S”表
示第2个操作，“3 C X”表示第3个操作。
【输出格式】
输出文件名为color.out。
对每个操作1，输出一个非负整数，表示区间内好数的个数。
【输入输出样例1】
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
数据规模与约定】
样例点编号 N M N个数大小(≤) 具有的操作
1，2 100 100 100 1,2,3
3,4 1000 1000 1000000 1,2,3
5,6,7 100000 100000 1000000 1,3
8,9,10 100000 100000 1000000 1,2,3
题解：
这个题目首先要打表找到好数的规律，不难发现只有2幂，质数以及6是好数，那么这个题目就可以预处理出1~100000中的所有的好数，用线性筛就可以了，知道这个东西之后题目就变成了统计区间好数的个数，用线段树维护就可以了，但这个题目要区间取模，因为对于一个数最多只要取模logn次就可以取模完成，所以只要在线段树中每次递归到叶子节点，暴力取就可以了，（当然模数>区间最大值时就不要模了）。
代码：（没写多组数据的，改一下就好了）
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <iostream> #define MAXN 1000015 #define MAXN2 100015 using namespace std; struct tree{ int l,r,x,shu,maxx; }a[MAXN2*4]; bool can[MAXN]; int zhi[MAXN2]; int n,m; void yvchuli(){ memset(can,1,sizeof(can)); can[0]=can[1]=0; for(int i=2;i<=1000000;i++){ if(can[i]){ for(int j=i*2;j<=1000000;j+=i) can[j]=0; } } can[0]=can[1]=can[6]=1; int now=2; while(now<=1000000) {can[now]=1;now*=2;} } void build(int xv,int l,int r){ if(l==r){ a[xv].l=l,a[xv].r=r; a[xv].shu=zhi[l],a[xv].maxx=zhi[l]; if(can[zhi[l]]) a[xv].x=1; else a[xv].x=0; return; } a[xv].l=l,a[xv].r=r; int mid=(l+r)/2; build(xv*2,l,mid);build(xv*2+1,mid+1,r); a[xv].maxx=max(a[xv*2].maxx,a[xv*2+1].maxx); a[xv].x=a[xv*2].x+a[xv*2+1].x; } int query(int xv,int l,int r){ int L=a[xv].l,R=a[xv].r,mid=(L+R)/2; if(l==L&&r==R){ return a[xv].x; } if(r<=mid) return query(xv*2,l,r); if(l>mid) return query(xv*2+1,l,r); return query(xv*2,l,mid)+query(xv*2+1,mid+1,r); } void change(int xv,int pos,int hh){ int l=a[xv].l,r=a[xv].r,mid=(l+r)/2; if(l==r&&l==pos){ a[xv].shu=hh; a[xv].maxx=hh; if(can[hh]) a[xv].x=1; else a[xv].x=0; return; } if(pos<=mid) change(xv*2,pos,hh); else change(xv*2+1,pos,hh); a[xv].x=a[xv*2].x+a[xv*2+1].x; a[xv].maxx=max(a[xv*2].maxx,a[xv*2+1].maxx); } void Ray(int xv,int l,int r,int S){ int L=a[xv].l,R=a[xv].r,mid=(L+R)/2; if(a[xv].maxx<S) return; if(L==R){ a[xv].shu%=S; a[xv].maxx=a[xv].shu; if(can[a[xv].shu]) a[xv].x=1; else a[xv].x=0; return; } if(r<=mid) Ray(xv*2,l,r,S); else if(l>mid) Ray(xv*2+1,l,r,S); else Ray(xv*2,l,mid,S),Ray(xv*2+1,mid+1,r,S); a[xv].x=a[xv*2].x+a[xv*2+1].x; a[xv].maxx=max(a[xv*2].maxx,a[xv*2+1].maxx); } int main() { yvchuli(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&zhi[i]); build(1,1,n); while(m--){ int id,x,y,z;scanf("%d%d%d",&id,&x,&y); if(id==1){ int numm=query(1,x,y); printf("%d ",numm); } else if(id==2){ scanf("%d",&z); Ray(1,x,y,z); } else change(1,x,y); } return 0; }