本人看到此題沒有翻譯，就附帶了一個自己的翻譯版本
思考
這一題，它的第一個要求是找出所有 \(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.uj5u.com/houduan/250.html
標籤：C++
上一篇：Codeforces 1400E Clear the Multiset(貪心 + 分治)
下一篇：統計區間素數數量