Description

我們定義一個(gè)非負(fù)整數(shù)是“好數(shù)”，當(dāng)且僅當(dāng)它符合以下條件之一：
1.這個(gè)數(shù)是0或1
2.所有小于這個(gè)數(shù)且與它互質(zhì)的正整數(shù)可以排成一個(gè)等差數(shù)列例如，8就是一個(gè)好數(shù)，因?yàn)?,3,5,7排成了等差數(shù)列。
給出N個(gè)非負(fù)整數(shù)，然后進(jìn)行如下三個(gè)操作：
1.詢問區(qū)間[L,R]有多少個(gè)好數(shù)
2.將區(qū)間[L,R]內(nèi)所有數(shù)對(duì)S取余(S≤1000000)
3.將第C個(gè)數(shù)更改為X

Input

第一行包含兩個(gè)正整數(shù)N和M，M表示操作數(shù)目
第二行包含N個(gè)非負(fù)整數(shù)。
接下來的M行每行表示1個(gè)操作：“1 L R”表示第1個(gè)操作，“2 L R S”表示第2個(gè)操作，“3 C X”表示第3個(gè)操作。

Output

對(duì)每個(gè)操作1，輸出一個(gè)非負(fù)整數(shù)，表示區(qū)間內(nèi)好數(shù)的個(gè)數(shù)。

Sample Input

Sample1:

3 6
4 6 9
1 1 3
1 3 3
2 1 1 10
1 1 3
3 2 4
1 1 3

Sample2:

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

Sample Output

Sample1:

2
0
2
2

Sample2:

3
6
4

Data Constraint

Solution

• 首先，我們暴力打表出較小的好數(shù)的情況。

• 接著就可以發(fā)現(xiàn)一些規(guī)律，“好數(shù)”一定是以下三種情況之一：

• 是 0 ，1 或 6 ；
• 是 質(zhì)數(shù) ；
• 是 2 的 i 次冪 。

• 于是我們用線性篩法篩出質(zhì)數(shù)、枚舉 i 次冪（預(yù)處理）。

• 那么我們就可以用一個(gè)布爾數(shù)組 O(1) 判斷出一個(gè)數(shù)是否是“好數(shù)”了。

• 觀察所給的三種操作，發(fā)現(xiàn)第 ① 、③ 種操作可以用線段樹直接維護(hù)。

• 但是第 ② 種操作我們沒有見過，直接暴力處理的話又會(huì)超時(shí)。怎么辦呢？

• 我們考慮做線段樹時(shí)多維護(hù)一個(gè)值——區(qū)間最大值。

• 當(dāng)處理到一個(gè)區(qū)間，模數(shù) S 比這個(gè)區(qū)間的最大值還大，那么繼續(xù)處理就沒有意義了。

• 否則直接暴力修改，這樣就不會(huì)超時(shí)了，可以證明操作次數(shù)不會(huì)很大。

Code

#include<cstdio> using namespace std; const int N=100001,M=N*10; struct data {int v,mx,s; }g[N<<2]; int a[N],f[M]; bool bz[M]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline int max(int x,int y) {return x>y?x:y; } inline void update(int v) {g[v].s=g[v<<1].s+g[v<<1|1].s;g[v].mx=max(g[v<<1].mx,g[v<<1|1].mx); } inline void build(int v,int l,int r) {if(l==r){g[v].v=g[v].mx=a[l];g[v].s=!bz[a[l]];return;}int mid=(l+r)>>1;build(v<<1,l,mid);build(v<<1|1,mid+1,r);update(v); } inline void change(int v,int l,int r,int x,int y) {if(l==r){g[v].v=g[v].mx=y;g[v].s=!bz[y];return;}int mid=(l+r)>>1;if(x<=mid) change(v<<1,l,mid,x,y); else change(v<<1|1,mid+1,r,x,y);update(v); } inline void modify(int v,int l,int r,int x,int y,int z) {if(g[v].mx<z) return;if(l==r){g[v].mx=g[v].v%=z;g[v].s=!bz[g[v].v];return;}int mid=(l+r)>>1;if(y<=mid) modify(v<<1,l,mid,x,y,z); elseif(x>mid) modify(v<<1|1,mid+1,r,x,y,z); else{modify(v<<1,l,mid,x,mid,z);modify(v<<1|1,mid+1,r,mid+1,y,z);}update(v); } inline int query(int v,int l,int r,int x,int y) {if(l==x && r==y) return g[v].s;int mid=(l+r)>>1;if(y<=mid) return query(v<<1,l,mid,x,y);if(x>mid) return query(v<<1|1,mid+1,r,x,y);return query(v<<1,l,mid,x,mid)+query(v<<1|1,mid+1,r,mid+1,y); } int main() {for(int i=2;i<M;i++){if(!bz[i]) f[++f[0]]=i;for(int j=1;j<=f[0] && i*f[j]<M;j++){bz[i*f[j]]=true;if(i%f[j]==0) break;}}bz[6]=false;for(int i=4;i<M;i<<=1) bz[i]=false;int n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();build(1,1,n);while(m--){int op=read(),l=read(),r=read();if(op==1) printf("%d\n",query(1,1,n,l,r));if(op==2) modify(1,1,n,l,r,read());if(op==3) change(1,1,n,l,r);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 100045. 【NOIP2017提高A组模拟7.13】好数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。