这一题，它的第一个要求是找出所有 \(7\) 位反向质数及其质因数的个数。
我们应该需要质数筛筛选1~\(10^{7}\)的所有数，这里就不慢慢介绍了。但是，重读题，我们突然发现反向质数都是 \(7\) 位，而将它反过来后的数字却是 \(6\) 位数，这就说明了最后一位数肯定是0，这样，我们就可以只筛到\(10^{6}\)，也就是说，筛所有反向数，如果是质数，反向过来，末尾填 \(0\) 就是了。这样，我们就减少了时间复杂度，这一部分函数的代码如下：
#define N 1e6+10
void Euler_prime() //欧拉筛
{
memset(is_prime,true,sizeof(is_prime)); //先全部标记为是质数
is_prime[1]=false; //特判一下1不是质数
for(int i=2;i<N;i++) //枚举2~N的每个数
{
if(is_prime[i]) prime[++tot]=i; //如果是质数
for(int j=1;j<=tot;j++)
{
if(prime[j]*i>N)
break;
is_prime[prime[j]*i]=false;
if(i%prime[j]==0)
break;
}
}
}
int solve(int num) //实现了num数的反向
{
int len=0,ret=0,bit[20];
while(num)
{
bit[len++]=num%10;
num/=10;
}
for(int i=0;i<len;i++)
{
ret=ret*10+bit[i];
} //本函数到这里实现了res=num的反向数
while(ret<100000) ret*=10; //因为求出来的数不一定是6位数，所以要加上这行代码，末尾填0
return ret;
}
这里求完了，接着就要算出它的质因数的个数，这个应该是非常简单的了。但是还要注意，因为我们是筛选的1~\(10^{6}\)的质数，再反过来在末尾填 \(0\) 的，顺序都被打乱了，所以我们要将所有反向质数从小到大排序。这里为了离散化，使用了 \(STL\) 库中的 \(map\)，不懂的同学可以自行百度一下。初始化的部分如下：
map<int,int>m; //为了能够离散化，我使用了map
void init() //初始化函数
{
Euler_prime(); //先筛了吧……
for(int i=1;i<=tot;i++)
a[i]=solve(prime[i]); //a[i]表示第prime[i]个数的反向质数
sort(a+1,a+1+tot); //此题需要从小到大排序，才能在后面的二分中查询
for(int i=1;i<=tot;i++)
m[a[i]]=i; //将其离散化
/*以下函数部分实现了求i的质因数*/
for(int i=1;i<=tot;i++)
{
fac[i]=2; //fac[i]用来贮存第i个反向质数的质因数的数量，初值一定要赋2
int tmp=a[i];
for(int j=1;j<=tot&&prime[j]*prime[j]<=tmp;j++)
{
while(tmp%prime[j]==0)
{
tmp/=prime[j];
fac[i]++;
}
}
if(tmp>1) fac[i]++; //在特殊情况下，tmp未除尽，质因数的数量要再加一个
}
}
现在，再来看看题目给我们的 \(2\) 个操作，一个是删除，一个是查询。如果我们用普通的模拟来解决的话，肯定是会超时的。这里，我们就会想到一种特殊的数据结构——树状数组，也就是此题的关键。由于题目的特殊性，这里，我们必须要定义两个树状数组，一个树状数组 \(c1\) 记录当前 \(i\) 节点之前有多少个数，而另一个 \(c2\) 记录了从第一个位置到当前位置反向质数的质因数的个数的总和。在查询时，我们还要注意一下，要找出第 \(0\) 到 \(i\) 的所有的反向质数的质因数的数量的累计总和，我们需要找出它的位置，因此可以用二分来解决这个问题，这时，问题就变得很简单。
树状数组的代码如下：
/**********以下是树状数组基本函数**********/
int lowbit(int k) //神奇的lowbit函数
{
return k&-k;
}
void add1(int x,int v) //
{
for(int i=x;i<N;i+=lowbit(i))
c1[i]+=v;
}
void add2(int x,int v) //
{
for(int i=x;i<N;i+=lowbit(i))
c2[i]+=v;
}
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;
}
/**********以上是树状数组基本函数**********/
int main()
{
init(); //初始化......
char op[2]; //因为一个字符的输入总是有问题，所以就定义字符串啦
int k;
for(int i=1;i<=tot;i++)
{
add1(i,1); //存在则压入数字1
add2(i,fac[i]); //当前位置有多少个反向质数
}
while(scanf("%s%d",op,&k)!=EOF) //输入
{
if(op[0]==‘q‘) //既然要输出0~i的所有反向质数，那么我们需要将它先在树状数组中找出来，才好输出总和
{
k++; //因为本人习惯于从1开始，而此题从0开始，只得k++
int l=1,r=tot,mid; //既然我们要将这个数在树状数组中找出，那么我们用二分是个不错的选择！
while(l<=r)
{
mid=(l+r)/2; //用mid变量来搜出k的位置
ll tmp=getsum1(mid); //记录一下mid的位置
if(tmp==k) //搜出来了就break
break;
else if(tmp<k) //如果当前的比k小，说明当前数左边的数也肯定也比k小，所以往右找
l=mid+1;
else //否则如果当前的比k大，说明当前数右边的数也肯定也比k大，所以往左找
r=mid-1;
}
printf("%lld\n",getsum2(mid)); //最后输出总和就好啦！
}
if(op[0]==‘d‘)
{
add1(m[k/10],-1); //不存在了就减去1，（就是把它删了）
add2(m[k/10],-fac[m[k/10]]); //将这个数从第一个位置到当前位置有多少个反向质数表为0（也是把它删了^_^）删数时因为转换的是6位数，所以要这里要/10
}
}
return 0;
}
呼——整篇文章就差不多了，我再把完整代码整合一下：
#include <bits/stdc++.h>
#define N 1000001 //宏定义一个最大值
#define ll long long //宏定义ll为long long (懒~）
using namespace std; //命名空间
bool is_prime[N]; //is_prime[i]表示的是i是否为质数，true则是，false则不是
int prime[N],tot=0,a[N],fac[N]; //prime存贮质数，tot存储质数有多少，a[i]记录了prime[i]的反向质数，fac[i]存储的是i的质因数的个数
ll c1[N],c2[N]; //这里要定义两个树状数组，一个树状数组c1记录当前i节点之前有多少个数，而另一个c2记录了从第一个位置到当前位置反向质数的质因数的个数的总和
map<int,int>m; //为了能够离散化，我使用了map
void Euler_prime() //欧拉筛
{
memset(is_prime,true,sizeof(is_prime));
is_prime[1]=false;
for(int i=2;i<N;i++)
{
if(is_prime[i]) prime[++tot]=i;
for(int j=1;j<=tot;j++)
{
if(prime[j]*i>N)
break;
is_prime[prime[j]*i]=false;
if(i%prime[j]==0)
break;
}
}
}
int solve(int num) //实现了num数的反向
{
int len=0,ret=0,bit[20];
while(num)
{
bit[len++]=num%10;
num/=10;
}
for(int i=0;i<len;i++)
{
ret=ret*10+bit[i];
} //本函数到这里实现了res=num的反向数
while(ret<100000) ret*=10; //因为求出来的数不一定是6位数，所以要加上这行代码
return ret;
}
void init() //初始化函数
{
Euler_prime(); //先筛了吧……
for(int i=1;i<=tot;i++)
a[i]=solve(prime[i]); //a[i]表示第prime[i]个数的反向质数
sort(a+1,a+1+tot); //此题需要排序
for(int i=1;i<=tot;i++)
m[a[i]]=i; //将其离散化
/*以下函数部分实现了求i的质因数*/
for(int i=1;i<=tot;i++)
{
fac[i]=2;
int tmp=a[i];
for(int j=1;j<=tot&&prime[j]*prime[j]<=tmp;j++)
{
while(tmp%prime[j]==0)
{
tmp/=prime[j];
fac[i]++;
}
}
if(tmp>1) fac[i]++; //在特殊情况下，要加一个
}
}
/**********以下是树状数组基本函数**********/
int lowbit(int k) //神奇的lowbit函数
{
return k&-k;
}
void add1(int x,int v) //
{
for(int i=x;i<N;i+=lowbit(i))
c1[i]+=v;
}
void add2(int x,int v) //
{
for(int i=x;i<N;i+=lowbit(i))
c2[i]+=v;
}
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;
}
/**********以上是树状数组基本函数**********/
int main()
{
init(); //初始化......
char op[2]; //因为一个字符的输入总是有问题，所以就定义字符串啦
int k;
for(int i=1;i<=tot;i++)
{
add1(i,1); //存在则压入数字1
add2(i,fac[i]); //当前位置有多少个反向质数
}
while(scanf("%s%d",op,&k)!=EOF) //输入
{
if(op[0]==‘q‘) //既然要输出0~i的所有反向质数，那么我们需要将它先在树状数组中找出来，才好输出总和
{
k++; //因为本人习惯于从1开始，而此题从0开始，只得k++
int l=1,r=tot,mid; //既然我们要将这个数在树状数组中找出，那么我们用二分是个不错的选择！
while(l<=r)
{
mid=(l+r)/2; //用mid变量来搜出k的位置
ll tmp=getsum1(mid); //记录一下mid的位置
if(tmp==k) //搜出来了就break
break;
else if(tmp<k) //如果当前的比k小，说明当前数左边的数也肯定也比k小，所以往右找
l=mid+1;
else //否则如果当前的比k大，说明当前数右边的数也肯定也比k大，所以往左找
r=mid-1;
}
printf("%lld\n",getsum2(mid)); //最后输出总和就好啦！
}
if(op[0]==‘d‘)
{
add1(m[k/10],-1); //不存在了就减去1，（就是把它删了）
add2(m[k/10],-fac[m[k/10]]); //将这个数从第一个位置到当前位置有多少个反向质数表为0（也是把它删了^_^）删数时因为转换的是6位数，所以要这里要/10
}
}
return 0;
}
/*
这么长的代码终于打完了，呼——
来总结一下：
- 看到质数，数量众多，首先想质数筛（推荐欧拉筛）
- 在资料一对一映射时，为了省时间省财富，我推荐STL的map
- 做题时，要找出树状数组的基本模型，判断树状数组维护什么，需要几个维护
- 在查找时，要学会使用二分，事半功倍
（其实主要还是树状数组，只不过加了一个质数筛，二分和一些操作而已）
*/
原文：https://www.cnblogs.com/Holy-Glory-Alex/p/uva11610.html