做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2289. -- 反转素数(树状数组)

2289: 反转素数(树状数组)

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[上一题][提交][讨论版][状态][下一题]

题目描述

满足自身的反序数是不超过106的素数的七位数被称做“反转素数”,例如1000070,1000090和1000240就是满足这样条件的前三个数。你首先需要找到所有的这样七位数的反转素数以及它们各自所包含的质因子个数。例如,24可以被因数分解为2*2*2*3,所以它包含了4个质因子。

输入

现在,你求出了所有这样的七位数后将它们从小到大排列,并进行一系列以下操作:

(1)查询:形如“q i”,你需要求出当前序列中第0个数到到i个数,这i个数各自的质因子个数和。

(2)删除:形如“d reverse_prime”,你需要将给定的反转素数reverse_prime,从序列中删除。注意:这种操作会影响到你的查询。

数据保证i是一个合法的下标,并且reverse_prime一定是一个反转素数,所删除的reverse_prime不会重复。

至多会有71000个查询与35000个删除操作。

输出

你需要读入数据直到文件结束。每行数据是一个字母加上一个数字,格式详见样例。

对于每个询问,输出一行一个整数,代表质因子个数和。

样例输入

q 0
q 1
q 2
d 1000070
d 1000090
q 0
d 1000240
q 0
q 1

样例输出

4
10
16
6
3
7

提示

《高级数据结构》习题6-3

来源:西班牙Valladolid大学 UVa 11610

标签

[上一题][提交][讨论版][状态][下一题]