【问题描述】
我们定义一个非负整数是“好数”，当且仅当它符合以下条件之一：
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】
good.in
3 6
4 6 9
1 1 3
1 3 3
2 1 1 10
1 1 3
3 2 4
1 1 3
good.out
2
0
2
2
【输入输出样例2】
good.in
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
good.out
3
6
4
【数据规模与约定】
样例点编号 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
【题解】
20分做法：
直接暴力判断区间内每个数是否是好数。
40分做法：
可以找规律发现好数的性质：它必须是质数、2的k次幂或者6。证明：如果不为质数，那么一定有2因子，否则1和2都与它互质。设为m*2^k(m是大于1的奇数),那么m+2和m-2与它互质，1和m*2^k – 1与它互质，数列确定为1,5,9,13,…，只有这个数为6的时候成立。
于是可以预处理出好数，处理操作的时间复杂度O(N*M)
70分做法：
发现没有操作2，用基本的线段树/树状数组做。
100分做法1：
加上操作2后，可以发现每个数取余后要么不变化，要么小于原来的二分之一，因此每个数X变化的次数至多为log(X)次，因此可以暴力修改它。在线段树上加上一个记录区间最大值的数，如果当前取余的数S大于这段区间最大值，那么就不用在其上取余。
100分做法2：
仍用树状数组，只是在处理k=2的情况时，若其是否为好数的性质不变，即不修改。
（但这样比前一种做法慢了不少）manlebushao
这道题反映出我的一个问题：树状数组/线段树掌握不熟练。同时，树状数组的模板是给当前值加数，若要他变成一个值，加后者与前者之差即可。
树状数组：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
int prime[1000001]={},cnt,n,m,c[100001]={},x,y,s,a[100001]={},t;
bool vis[1000001]={};
il int gi()
{
re int x=0;
re short int t=1;
re char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
void add(int p,int v)
{
while(p<=n)
a[p]+=v,p+=p&-p;
}
int pre(int p)
{
if(!p) return 0;
int s;
for(s=0;p;p-=p&-p)
s+=a[p];
return s;
}
void Prime(int n)
{
vis[1]=1;
for(int i=2;i<=n;i++)
{
if(!vis[i])
prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(!(i%prime[j]))
break;
}
}
}
int main()
{
freopen("good.in","r",stdin);
freopen("good.out","w",stdout);
Prime(1000000);
vis[0]=0;vis[1]=0;vis[6]=0;
fp(i,1,19)
vis[1<<i]=0;//预处理好数
n=gi();m=gi();
fp(i,1,n)
c[i]=gi(),add(i,!vis[c[i]]);
fp(i,1,m)
{
int k=gi();x=gi();y=gi();
if(k==1) printf("%d
",pre(y)-pre(x-1));
if(k==2)
{
s=gi();
fp(j,x,y)
if(c[j]>=s)
{
int last=!vis[c[j]];
c[j]%=s;
add(j,!vis[c[j]]-last);
}
}
if(k==3)
{
int last=!vis[c[x]];
add(x,!vis[y]-last);
c[x]=y;
}
}
return 0;
}附上线段树做法：
#include <bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define N (1000010)
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;
int prime[N],vis[N],phi[N],a[N],n,m,cnt;
int can[N<<2],mx[N<<2];
il int gi(){
RG int x=0,q=1; RG char ch=getchar();
while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
if (ch=='-') q=-1,ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
return q*x;
}
il void pre(){
phi[1]=1;
for (RG int i=2;i<N;++i){
if (!vis[i]) prime[++cnt]=i,phi[i]=i-1;
for (RG int j=1,k;j<=cnt;++j){
k=i*prime[j]; if (k>=N) break; vis[k]=1;
if (i%prime[j]) phi[k]=phi[i]*(prime[j]-1);
else{ phi[k]=phi[i]*prime[j]; break; }
}
}
for (RG int i=1;i<N;i<<=1) vis[i]=0; return;
}
il int check(RG int x){ return !vis[x] || phi[x]<=2; }
il void pushup(RG int x){
can[x]=can[ls]+can[rs];
mx[x]=max(mx[ls],mx[rs]); return;
}
il void build(RG int x,RG int l,RG int r){
if (l==r){ mx[x]=a[l],can[x]=check(a[l]); return; }
RG int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(x); return;
}
il void update(RG int x,RG int l,RG int r,RG int p,RG int v){
if (l==r){ mx[x]=v,can[x]=check(v); return; } RG int mid=(l+r)>>1;
p<=mid ? update(ls,l,mid,p,v) : update(rs,mid+1,r,p,v);
pushup(x); return;
}
il void updatemod(RG int x,RG int l,RG int r,RG int xl,RG int xr,RG int S){
if (l==r){ mx[x]%=S,can[x]=check(mx[x]); return; }
if (mx[x]<S) return; RG int mid=(l+r)>>1;
if (xr<=mid) updatemod(ls,l,mid,xl,xr,S);
else if (xl>mid) updatemod(rs,mid+1,r,xl,xr,S);
else updatemod(ls,l,mid,xl,mid,S),updatemod(rs,mid+1,r,mid+1,xr,S);
pushup(x); return;
}
il int query(RG int x,RG int l,RG int r,RG int xl,RG int xr){
if (xl<=l && r<=xr) return can[x]; RG int mid=(l+r)>>1;
if (xr<=mid) return query(ls,l,mid,xl,xr);
else if (xl>mid) return query(rs,mid+1,r,xl,xr);
else return query(ls,l,mid,xl,mid)+query(rs,mid+1,r,mid+1,xr);
}
int main(){
n=gi(),m=gi(),pre();
for (RG int i=1;i<=n;++i) a[i]=gi();
build(1,1,n);
for (RG int i=1,op,l,r,S,c,x;i<=m;++i){
op=gi();
if (op==1){
l=gi(),r=gi();
printf("%d
",query(1,1,n,l,r));
}
if (op==2){
l=gi(),r=gi(),S=gi();
updatemod(1,1,n,l,r,S);
}
if (op==3){
c=gi(),x=gi();
update(1,1,n,c,x);
}
}
return 0;
}