题目地址：ZJU 3886
这个题需要想到一点，因为对一个数x不断取模的话，而且设定他小于模才会进行取余操作的话，那么最多只会进行logx次，因为每次取模都会使x最少折半。然后想到了这点就很好做了。对于区间取模更新操作可以直接暴力更新，维护一个最大值，如果这个区间的最大值小于模的话， 就不用继续向叶子更新了。然后其他的大于模的就更新到叶子节点。
然后对于NicoNumber来说，只有6，2的幂次和素数来说是符合的。所以可以预处理出来。然后就可以用线段树来维护了。
代码如下： #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long #define pi acos(-1.0) #pragma comment(linker, "/STACK:1024000000") #define root 1, n, 1 #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e-9; const int MAXN=100000+10; bool isprime[MAXN*100], ok[MAXN*100]; int prime[MAXN*10]; int Max[MAXN<<2], sum[MAXN<<2]; void init() { int tot=0, i, j; ok[0]=ok[1]=1; ok[6]=1; for(i=2;i<=10000000;i++){ if(!isprime[i]) { prime[tot++]=i; ok[i]=true; } for(j=0;jif(i*prime[j]>10000000) break; isprime[i*prime[j]]=true; if(i%prime[j]==0) break; } } int x=2; while(x<=10000000){ ok[x]=true; x<<=1; } } void PushUp(int rt) { Max[rt]=max(Max[rt<<1],Max[rt<<1|1]); sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void Build(int l, int r, int rt) { if(l==r){ scanf("%d",&Max[rt]); sum[rt]=ok[Max[rt]]; return ; } int mid=l+r>>1; Build(lson); Build(rson); PushUp(rt); } void Update1(int p, int x, int l, int r, int rt) { if(l==r){ Max[rt]=x; sum[rt]=ok[x]; return ; } int mid=l+r>>1; if(p<=mid) Update1(p,x,lson); else Update1(p,x,rson); PushUp(rt); } void Update2(int ll, int rr, int x, int l, int r, int rt) { if(ll<=l&&rr>=r){ if(Max[rt]return ; } if(l==r){ Max[rt]%=x; sum[rt]=ok[Max[rt]]; return ; } int mid=l+r>>1; if(ll<=mid) Update2(ll,rr,x,lson); if(rr>mid) Update2(ll,rr,x,rson); PushUp(rt); } int Query(int ll, int rr, int l, int r, int rt) { if(ll<=l&&rr>=r){ return sum[rt]; } int mid=l+r>>1, ans=0; if(ll<=mid) ans+=Query(ll,rr,lson); if(rr>mid) ans+=Query(ll,rr,rson); return ans; } int main() { int n, i, j, l, r, p, v, q, x; init(); while(scanf("%d",&n)!=EOF){ memset(Max,0,sizeof(Max)); memset(sum,0,sizeof(sum)); Build(root); scanf("%d",&q); while(q--){ scanf("%d",&x); if(x==1){ scanf("%d%d",&l,&r); printf("%d ",Query(l,r,root)); } else if(x==2){ scanf("%d%d%d",&l,&r,&v); Update2(l,r,v,root); } else{ scanf("%d%d",&p,&v); Update1(p,v,root); } } } return 0; }