uva11610 树状数组+素数打表求因子，好题！

/* uva11610 树状数组+素数打表+离散化 打出的素数范围在2-1000000之间，不超过六位数，然后按照格式翻转成七位数 */ #include<bits/stdc++.h> using namespace std; #define maxn 1000005 #define ll long long int flag[maxn],prime[maxn],cnt; int fac[maxn],a[maxn],tot,p[maxn]; ll bit1[maxn],bit2[maxn]; map<int,int>m; int solve(int num){//将每个素数翻转后返回，最后一位必定是0，忽略 int len=0,ret=0,bit[20]; while(num){ bit[len++]=num%10; num/=10; } for(int i=0;i<len;i++) ret=ret*10+bit[i]; while(ret<100000) ret*=10; return ret; } void init(){ for(int i=2;i<1000000;i++){//线性筛 if(flag[i])continue; prime[++cnt]=i; for(int j=2;j*i<1000000;j++) flag[i*j]=1; } for(int i=1;i<=cnt;i++)//将每个素数翻转 a[i]=solve(prime[i]); sort(a+1,a+1+cnt); for(int i=1;i<=cnt;i++)//离散化 m[a[i]]=i; for(int i=1;i<=cnt;i++){ fac[i]=2;//删掉最后一个0带来的两个质因数 int tmp=a[i]; for(int j=1;j<=cnt && prime[j]*prime[j]<=tmp;j++) while(tmp%prime[j]==0){ tmp/=prime[j]; fac[i]++; } if(tmp>1) fac[i]++; } } void add1(int x,int num){ for(int i=x;i<=maxn-3;i+=i&-i) bit1[i]+=num; } void add2(int x,int num){ for(int i=x;i<=maxn-3;i+=i&-i) bit2[i]+=num; } ll query1(int x){ ll res=0; for(int i=x;i;i-=i&-i) res+=bit1[i]; return res; } ll query2(int x){ ll res=0; for(int i=x;i;i-=i&-i) res+=bit2[i]; return res; } int main(){ init(); for(int i=1;i<=cnt;i++){ add1(i,1); add2(i,fac[i]); } char op[5];int k; while(scanf("%s%d",op,&k)!=EOF){ if(op[0]=='d'){//把整个点从数组中删除 add1(m[k/10],-1); add2(m[k/10],-fac[m[k/10]]); } else { k++; int l=1,r=cnt,ans; while(l<=r){ int mid=l+r>>1; ll tmp=query1(mid); if(tmp<=k) ans=mid,l=mid+1; else r=mid-1; } printf("%lld\n",query2(ans)); } } return 0; }

 

转载于:https://www.cnblogs.com/zsben991126/p/10114286.html

相关资源：各显卡算力对照表！