UVA11610-Reverse Prime

作者 macorhard

Description

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.

题目大意

定义了一种叫做Reverse Prime的数：

位数为7位，倒转之后是六位的素数

要求按顺序找出所有的Reverse Prime，并计算出每个Reverse Prime的因子数

可以对这些数进行一下两种操作：

1、“q i”查询区间[0,i]Reverse Prime的因子数之和

2、“d reverse_prime”把reverse_prime这个Reverse Prime从序列中删除

Part 1

对于每个Reverse Prime，我们可以按照定义， Reverse Prime的倒序是一个六位数，而Reverse Prime本身是一个七位数，那么我们可以知道Reverse Prime的最后一位一定是0；

那么对于每一个Reverse Prime，求出所有的六位的素数，将其倒序的末尾加上一个0就是Reverse Prime了

求素数是可以使用埃拉托斯特尼筛法

然后。。。打表出奇迹打出素数表

Part 2

对于每个处理好的Reverse Prime，我们求出它的的因数。然后依照题意排序。

对于求第几个Reverse Prime我们建立一个树状数组用来记录位置0到位置i有多少个Reverse Prime

对于第一个操作，用二分查找当前序列第i个Reverse Prime的位置.

这里就需要求区间第k大的数，可以用树状数组来解决。：建一个权值树状数组。求第k大的数，不就是求getsum[1,val]≈k的数。

然后求因子数的前缀和。 

然而暴力枚举依然会超出时间上线。

但是。我们要求的是前缀和—

于是我们可以建立第二个树状数组来记录因数！

对于第二个操作：

给定了Reverse Prime的值

但是仍然不方便找到Reverse Prime

由于对Reverse Prime进行离散化了，可以直接找到这个Reverse Prime所在的位置。

然后把这个位置上的Reverse Prime值置为0即可，同时也将第一个树状数组的个数-1。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct NODE
{
	int b;
	int pr;
} ;
NODE  s[1000005];
int a[1000005],q1[1000005],q2[1000005],f[1000005],ans,id[1000005];
int lowbit(int x)
{
	return x&-x;
}
int sum(int *c,int x)
{
	int ret=0;
	while(x>0)
	{
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
void add(int *c,int x,int d)
{
	while(x<=ans)
	{
		c[x]+=d;
		x+=lowbit(x);
	}
}
void prime()
{
	long long  i,j;
	ans=0;
	memset(a,0,sizeof(a));
	memset(f,0,sizeof(f));
	for(i=2; i<=100000; i++)
		if(!f[i])
		{
			a[++ans]=i;
			for(j=i*i; j<=100000; j+=i)
				if(!f[j]) f[j]=i;
		}
}
void fac(int i,int sum)
{
	while(sum%2==0)
	{
		s[i].pr++;
		sum/=2;
	}
	while(f[sum])
	{
		s[i].pr++;
		sum/=f[sum];
	}
	if(sum!=1) s[i].pr++;
}
void deal(int x,int p)
{
	int sum=0;
	while(x)
	{
		sum=sum*10+x%10;
		x/=10;
	}
	while(sum<100000)
		sum*=10;
	s[p].pr=2;
	fac(p,sum/10);
	s[p].b=sum;
}
void solve()
{
	int i;
	for(i=1; i<=ans; i++)
		deal(a[i],i);
}
bool cmp(NODE x,NODE y)
{
	return x.b<y.b;
}
int main()
{
	char ch[5];
	int i,t,l,r,m;
	memset(s,0,sizeof(s));
	memset(q1,0,sizeof(q1));
	memset(q2,0,sizeof(q2));
	prime();
	solve();
	sort(s+1,s+ans+1,cmp);
	for(i=1; i<=ans; i++)
		add(q2,i,s[i].pr);
	for(i=1; i<=ans; i++)
	{
		id[s[i].b]=i;
		add(q1,i,1);
	}
	while(scanf("%s",ch)!=EOF)
	{
		scanf("%d",&i);
		if(ch[0]=='q')
		{
			++i;
			l=1;
			r=ans;
			while(l<=r)
			{
				m=(l+r)>>1;
				t=sum(q1,m);
				if(t==i) break;
				if(t>i)
					r=m-1;
				else
					l=m+1;
			}
			printf("%d\n",sum(q2,m));
		}
		else
		{
			t=id[i];
			add(q1,t,-1);
			add(q2,t,-s[t].pr);
		}
	}
	return 0;
}

留下评论