Java教程

UVA11610 Reverse Prime

本文主要是介绍UVA11610 Reverse Prime,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Description

洛谷传送门

有一些小于\(10^6\)的质数,你需要把它们倒过来并补成一个 7 位数,例如质数 700001,将转变成 1000070,900001,将转变为 1000090,你要将转变后的数存成一个序列。输入有两种操作:

  1. 查询:输入q i,你需要输出这个序列中前 \(i\) 小(包含 \(i\) )的数的质因数个数的和。(注意是个数)

  2. 删除:输入d i,你需要把序列中第 \(i\) 小的数删除。

有多组输入

注意下角标从0开始

Solution

这道题我们考虑用树状数组解,首先我们用线性筛算出小于\(10^6\)的质数,并将这些质数倒过来补成 7 位数并存到一个数组里(比如说 \(a\) 数组),然后对 \(a\) 数组进行排序,再计算出 \(a\) 数组中每一个 7 位数的质因数个数存到另一个数组里,这样我们的预处理部分就完成了。

再来说如何做树状数组,我们需要两个树状数组,一个维护当前 \(i\) 节点之前有多少个数,另一个维护 \(i\) 节点之前所有数的质因数个数,我们需要将所有经过转变后的数都加进树状数组里,查询时利用二分查找一个有 \(i\) 个比本身小的数,删除时只需要把 -1 加进第一个树状数组,把该点的质因数个数的相反数加进第二个数状数组即可。

有一些小技巧,当计算每一个转换后的数的质因数个数时,由于质数最大也小于 7 位数,变为 7 位数至少多一个 0,所以直接让每一个数的质因数个数的初值为 2(10 可以拆成 \(2 * 5\)),质数转换时只转换为为 6 位数就可以了,可以看代码理解一下。

Code

#include <iostream>
#include <algorithm>
#include <map>
#define ll long long //答案是long long
#define N 1000000	 //质数的最大范围
#define M 100010	 //小于10^6的质数个数是78498个,这里开到100010

using namespace std;

map<int, int> mp;					//由于数据范围过大,需要开map,其实也可以用离散化,不过我太蒻了,所以用的map
int p[N + 10], mindiv[N + 10], tot; //线性筛用的,tot为质数个数
int a[N + 10];						//记录转换后的7位数
int c1[N + 10], c2[N + 10];			//树状数组,c1记录数的个数,c2记录质因数个数
int c[M];							//记录每一个数的质因数个数

//----------------------树状数组模板,不细讲了,有两个树状数组,所以要写两遍.
int lowbit(int k){
	return k & (-k);
}

void add1(int x, int y){
	for(int i = x; i <= N; i += lowbit(i)) //没有固定数据范围,所以要到最大值
		c1[i] += y;
}

void add2(int x, int y){
	for(int i = x; i <= N; i += lowbit(i))
		c2[i] += y;
}

ll getsum1(int x){
	ll ans = 0;
	for(int i = x; i > 0; i -= lowbit(i))
		ans += c1[i];
	return ans;
}

ll getsum2(int x){
	ll ans = 0;
	for(int i = x; i > 0; i -= lowbit(i))
		ans += c2[i];
	return ans;
}

//----------------------线性筛模板,也不讲了
void prime(){
	for(int i = 2; i <= N; i++){
		if(!mindiv[i]){
			mindiv[i] = i;
			p[++tot] = i;
		}
		for(int j = 1; j <= tot && p[j] * i <= N && p[j] <= mindiv[i]; j++)
			mindiv[p[j] * i] = p[j];
	}
}

//----------------------计算每一个经过转换后的6位数的质因数个数,至于为什么是6位数,请见代码上方的解释
void devide(int i){
	c[i] = 2;
	int tmp = a[i];
	for(int j = 1; j <= tot && p[j] * p[j] <= tmp; j++) //小优化,如果p[j]*p[j]>tmp,就不会再有tmp的质因数
		while(tmp % p[j] == 0)
			c[i]++, tmp /= p[j];
	if(tmp > 1) c[i]++;
}

//----------------------zh=转换,把每一个质数转换为新的6位数,值存在a数组中
int zh(int x){
	int ans = 0, t = 0;
	while(x)
		t++, ans = ans * 10 + x % 10, x /= 10;
	t = 6 - t;
	while(t)
		ans *= 10, t--;
	return ans;
}

//----------------------预处理
void prework(){
	for(int i = 1; i <= tot; i++) //转换
		a[i] = zh(p[i]);
	sort(a + 1, a + tot + 1);	   //从小到大排序
	for(int i = 1; i <= tot; i++) //存到map中
		mp[a[i]] = i;
	for(int i = 1; i <= tot; i++) //计算每一个转换后的数的质因数个数
		devide(i);
}

int main(){
	prime();
	prework();
	for(int i = 1; i <= tot; i++){ //初始化树状数组
		add1(i, 1);
		add2(i, c[i]);
	}
	char ch[5];
	int x;
	while(scanf("%s%d", ch, &x) != EOF){
		if(ch[0] == 'q'){
			x++;					 //注意,题目中下角标从0开始,这里从1开始算,所以加1
			int l = 1, r = tot, mid; //二分找答案,mid就是答案
			while(l <= r){
				mid = (l + r) >> 1;
				ll tmp = getsum1(mid);
				if(tmp == x) break;
				if(tmp < x) l = mid + 1;
				else r = mid - 1;
			}
			printf("%lld\n", getsum2(mid));
		}else{ //删数时因为转换的是6位数,所以要/10
			add1(mp[x / 10], -1);
			add2(mp[x / 10], -c[mp[x / 10]]);
		}
	}
	return 0;
}

End

这篇关于UVA11610 Reverse Prime的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!