首页 > 代码库 > uva 11610 Reverse Prime
uva 11610 Reverse Prime
Problem F
Reverse Prime
Input: Standard Input
Output: Standard Output
There are a few 7 digit positive numbers whose reverse number is a prime number and less than 10^6. For example: 1000070, 1000090 and 1000240 are first few reverse prime numbers because all of the numbers are 7 digit numbers whose reverse number is a prime number and less than 10^6. You have to find out all the 7 digit reverse prime numbers and also it?s number of prime factors. Prime factors of a positive integer are the prime numbers that divide into that integer exactly, without leaving a remainder. For example, prime factors of 24 are 2, 2, 2 and 3.
In this problem, you?ll encounter 2 types of input ?
Query:
This type of input will be formatted like this ? ?q i?. For this input, you have to calculate the cumulative summation of the number of prime factors of reverse prime numbers from 0-th to i-th index.
Deletion:
This type of input will be formatted like this ? ?d reverse_prime?. For this input, you have to delete reverse_prime from the set and update your summation. No output is required in such cases.
It is guaranteed that i will be a valid index and reverse_prime will be a valid 7 digit reverse prime number. It is also guaranteed that no two reverse_prime will be same.
There will be at most 71000 query lines and 3500 deletion lines in the data set. The program will terminated by EOF.
Sample Input Output for Sample Input
q 0 q 1 q 2 d 1000070 d 1000090 q 0 d 1000240 q 0 q 1 | 4 10 16 6 3 7
|
int getsum(int tmp){ int sum=0; for(int i=0;i<cnt&&prim[i]*prim[i]<=tmp;i++) if(tmp%prim[i]==0){ while(tmp%prim[i]==0){ sum++; tmp/=prim[i]; } if(tmp==1) return sum; } if(tmp>1) return ++sum;}
叼叼的
map<int ,int >Lk;
用map型的Lk 来影射每个resver数的位置
用到两个树状树状
一个树状树状是记录从第一个位置到当前位置的和
另一个是记录从第一个位置到当前位置有多少个resver数
q num
q 查询时 用二分的方法查找第num+1个数的位置，然后输出结果
d num
删除的时候 用Lk找到num这个数的位置，判断它是否已经被删除，如果没有则更新两个树状数组 1 #include<iostream> 2 #include<string> 3 #include<cstdio> 4 #include<vector> 5 #include<queue> 6 #include<stack> 7 #include<algorithm> 8 #include<cstring> 9 #include<stdlib.h> 10 #include<string> 11 #include<cmath> 12 #include<map> 13 using namespace std; 14 #define pb push_back 15 #define LL __int64 16 int p[101010],m,mm,prim[101010],cnt,vit[1001010],fuck[101010]; 17 map<int ,int >Lk; 18 struct node{ 19 int num; 20 int bf; 21 int id; 22 }check[101010]; 23 int cmp(node a,node b){ 24 return a.bf<b.bf; 25 } 26 void getprim(){ 27 cnt=0; 28 memset(vit,0,sizeof(vit)); 29 for(int i=2;i<1000000;i++){ 30 if(vit[i]) continue; 31 prim[cnt++]=i; 32 for(int j=2;j*i<1000000;j++) 33 vit[i*j]=1; 34 } 35 // cout<<"cnt=="<<cnt<<endl; 36 } 37 int getsum(int tmp){ 38 int sum=0; 39 for(int i=0;i<cnt&&prim[i]*prim[i]<=tmp;i++) 40 if(tmp%prim[i]==0){ 41 while(tmp%prim[i]==0){ 42 sum++; 43 tmp/=prim[i]; 44 } 45 if(tmp==1) return sum; 46 } 47 if(tmp>1) return ++sum; 48 } 49 void getrever(){ 50 int ko[10]; 51 for(int i=0;i<cnt;i++){ 52 int a=prim[i]; 53 int sum=0; 54 while(a){ 55 ko[sum++]=a%10;a/=10; 56 } 57 int tmp=0,so=1000000; 58 for(int j=0;j<sum;j++){ 59 tmp+=so*ko[j]; 60 so/=10; 61 } 62 check[i].bf=tmp; 63 check[i].num=getsum(tmp); 64 check[i].id=i; 65 } 66 sort(check,check+cnt,cmp); 67 for(int i=0;i<cnt;i++) 68 check[i].id=i+1; 69 } 70 void update(int pos,int num){ 71 while(pos<=cnt){ 72 p[pos]+=num; 73 pos+=pos&(-pos); 74 } 75 } 76 int getnum(int pos){ 77 int sum=0; 78 while(pos>0){ 79 sum+=p[pos]; 80 pos-=pos&(-pos); 81 } 82 return sum; 83 } 84 void init(){ 85 getprim(); 86 getrever(); 87 memset(p,0,sizeof(p)); 88 memset(fuck,0,sizeof(fuck)); 89 //cout<<"****"<<endl; 90 } 91 void update2(int pos,int num){ 92 while(pos<=cnt){ 93 fuck[pos]+=num; 94 pos+=pos&(-pos); 95 } 96 } 97 int getnum2(int pos){ 98 int sum=0; 99 while(pos>0){100 sum+=fuck[pos];101 pos-=pos&(-pos);102 }103 return sum;104 }105 int main(){106 init();107 for(int i=0;i<cnt;i++){108 update(i+1,check[i].num);109 Lk[check[i].bf]=i+1;110 update2(i+1,1);111 }112 char love[10];113 int pos;114 while(scanf("%s%d",love,&pos)!=EOF){115 if(love[0]==‘q‘){116 int l=1,r=cnt,mid,tt=cnt;;117 while(l<=r){118 mid=(l+r)/2;119 int tmp=getnum2(mid);120 if(tmp>=pos+1)121 r=mid-1;122 if(tmp<pos+1)123 l=mid+1;124 if(tmp==pos+1)125 tt=min(tt,mid);126 }127 printf("%d\n",getnum(tt));128 }129 else if(getnum2(Lk[pos])-getnum2(Lk[pos]-1)){130 // cout<<"*****"<<endl;131 update(Lk[pos],-check[Lk[pos]-1].num);132 update2(Lk[pos],-1);133 }134 }135 }