Coprimes Gym - 101492C(bitset)-白红宇

Coprimes Gym - 101492C(bitset)

阅读量：4700 次

发布时间：2019-06-09

本文共 1843 字，大约阅读时间需要 6 分钟。

思路：处理每一位右边第一组互质的数的右边数的位置，O(1)处理查询；

我们先处理对于一个数右边第一个与它互质的数

从n->1开始

对于每一个数对其进行素因数分解，记录每一个素数被那些数所包含

同时二进制标记处理其本身与那些数不互质

最后对i-n取反找第一个1出现的位置，就是右边与它互质的第一个数的位置

这样我们处理完了右边第一个和它互质数的位置，

对于第i个数右边第一对互质的数的右边数的位置应是 min(ans[i],ans[i+1],....ans[n]);

如果n->1跑的的就可以写成min(ans[i],ans[i+1]) ps:处理i时i+1已经处理结束；

这样就可以O(1)处理答案了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #define inf 0x3f3f3f3f#define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define sd(x) scanf("%d",&(x))#define sl(x) scanf("%lld",&(x))#define slf(x) scanf("%lf",&(x))#define scs(s) scanf("%s",s)#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)#define lowbit(x) x&(-x)#define ls now<<1#define rs now<<1|1#define lson l,mid,ls#define rson mid+1,r,rs#define All L,Rusing namespace std;const int maxn=5e4+10;int is_prime[maxn*10],prime[maxn],ans[maxn],a[maxn],tot=0,has[maxn*10];bitset
                
                  dp[maxn],mark,ok;void make(){ is_prime[1]=is_prime[0]=true; for(int i=2;i<=5e5;i++) { if(!is_prime[i]) { prime[++tot]=i; } for(int j=1;j<=tot&&i*prime[j]<=5e5;j++) { is_prime[i*prime[j]]=true; if(i%prime[j]==0) { break; } } }}int main(){ int n,m; make(); for(int i=0;i
                 
                  >n>>m; rep(i,1,n) cin>>a[i]; ans[n+1]=maxn; for(int i=n;i>=1;i--) { mark.reset(); mark[i]=1; ok[i]=1; for(int j=1;prime[j]*prime[j]<=a[i];j++) { if(a[i]%prime[j]==0&&a[i]) { dp[has[prime[j]]][i]=1; mark|=dp[has[prime[j]]]; } while(a[i]%prime[j]==0&&a[i]) { a[i]/=prime[j]; } } if(a[i]) dp[has[a[i]]][i]=1,mark|=dp[has[a[i]]]; ans[i]=(mark^ok)._Find_first(); ans[i]=min(ans[i],ans[i+1]); } while(m--) { int l,r; cin>>l>>r; if(ans[l]<=r) cout<<"S\n"; else cout<<"N\n"; } return 0;}