当前位置:编程学习 > C/C++ >>

UVA 11610 Reverse Prime(数论+树状数组+二分)

给出一个reverse_prime,自身是一个7位数,反转后是一个<=1e6的素数。
首先求出所有的这种数
两种操作
q k :表示删除数字K
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2657

首先预处理出所有的reverse_prime,我的做法是先打出<=1e6的所有素数
然后将其反转,可以看出所有素数都是6位数,但是题目要求是7位数,可见原数的最低位都为0,可以不考虑这个0,之后的效率也许会快点。
将所有素数反转,然后凑成6位数。再算出每个数的素因子个数,不要忘记之前少算的末尾的0,也就是因子2和因子5.
对于统计部分,建立两个树状数组,第一 个表示区间内还有多少个数,第二个表示区间内因子个数和。
对于D操作, 直接用map记录某个reverse_prime的下标,然后更新两个树状数组
对于q操作,二分位置,然后用第一个树状数组,可以知道区间内有多少个数。最后用第二个树状数组求和。
[cpp]
#include<iostream>    
#include<cstdio>    
#include<map>    
#include<cstring>    
#include<cmath>    
#include<vector>    
#include<algorithm>    
#include<set>    
#include<string>    
#include<queue>    
#define inf 1600005    
#define M 40    
#define N 1000000   
#define maxn 300005    
#define eps 1e-12  
#define zero(a) fabs(a)<eps    
#define Min(a,b) ((a)<(b)?(a):(b))    
#define Max(a,b) ((a)>(b)?(a):(b))    
#define pb(a) push_back(a)    
#define mp(a,b) make_pair(a,b)    
#define mem(a,b) memset(a,b,sizeof(a))    
#define LL unsigned long long    
#define MOD 1000000007  
#define lson step<<1  
#define rson step<<1|1  
#define sqr(a) ((a)*(a))    
#define Key_value ch[ch[root][1]][0]    
#define test puts("OK");    
#define pi acos(-1.0)  
#define lowbit(x) ((-(x))&(x))  
#pragma comment(linker, "/STACK:1024000000,1024000000")    
using namespace std; 
int flag[N]={0},prime[N],cnt=0; 
int fac[N],a[N],tot=0,p[N]; 
LL s1[N],s2[N]; 
map<int,int>m; 
int slove(int num){ 
    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<N;i++){ 
        if(flag[i]) continue; 
        prime[++cnt]=i; 
        for(int j=2;j*i<N;j++) 
            flag[i*j]=1; 
    } 
    for(int i=1;i<=cnt;i++){ 
        a[i]=slove(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,肯定包括2,5两个因子  
        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 Update(LL *s,int x,int val){ 
    for(int i=x;i<=cnt;i+=lowbit(i)) 
        s[i]+=val; 

LL sum(LL *s,int x){ 
    LL ret=0; 
    for(int i=x;i>0;i-=lowbit(i)) 
        ret+=s[i]; 
    return ret; 

int main(){ 
    //freopen("in.txt","r",stdin);  
    Init(); 
    char str[5];int k; 
    mem(s1,0);mem(s2,0); 
    for(int i=1;i<=cnt;i++) s1[i]=lowbit(i); 
    for(int i=1;i<=cnt;i++) Update(s2,i,fac[i]); 
    while(scanf("%s%d",str,&k)!=EOF){ 
        if(str[0]=='d'){ 
            int pos=m[k/10]; 
            Update(s1,pos,-1); 
            Update(s2,pos,-fac[pos]); 
        } 
        else{ 
            k++;  www.zzzyk.com
            int low=1,high=cnt,mid; 
            while(low<=high){ 
                mid=(low+high)>>1; 
                LL tmp=sum(s1,mid); 
                if(tmp==k) break; 
                if(tmp<k) low=mid+1; 
                else high=mid-1; 
            } 
            printf("%lld\n",sum(s2,mid)); 
        } 
    } 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,