uva 11610 Reverse Prime

时间：2014-08-03 23:07:36 阅读：567 评论：0 收藏：0 [点我收藏+]

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

先要得到小于1000000的素数

然后对每一个素数求它的Reverse，并填成7位，求出reverse后的输的所有的素数因子个数（可以有重复的素数因子）

一开始一直tle, 百度了一下题解，发现一个漂亮的剪枝

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 }

uva 11610 Reverse Prime,布布扣,bubuko.com

uva 11610 Reverse Prime

原文：http://www.cnblogs.com/ainixu1314/p/3889020.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)