d423 - 10856 - Recover Factorial
題目描述
題目給定一個整數 N，代表某個階乘 X! 的質因數個數。要求找出最小的 X，使得 X! 的質因數個數等於 N。如果找不到這樣的 X，則輸出 "Not possible."。
解題思路
這題的核心在於計算一個數字的階乘的質因數個數。直接計算每個階乘的質因數個數效率太低。因此，我們需要預先計算出每個質數對不同階乘的貢獻。
- 質數篩選: 首先，使用埃拉托斯特尼篩法找出 10000000 範圍內的質數。
- 質因數個數計算: 對於每個數字 i，計算其階乘的質因數個數。如果 i 是質數，則其貢獻為 1。如果 i 是合數，則分解 i 為質因數，並遞歸計算其質因數的個數。
- 預計算: 將每個質因數個數與對應的 X 儲存在一個 map 中。
- 查詢: 對於每個輸入的 N，在 map 中查找是否存在對應的 X。如果存在，則輸出 X!，否則輸出 "Not possible."。
複雜度分析
- 時間複雜度: O(N log log N + Q)，其中 N 是 10000000，Q 是查詢次數。O(N log log N) 是篩選質數的複雜度，O(Q) 是查詢的複雜度。
- 空間複雜度: O(N)，用於儲存質數和質因數個數的 map。
程式碼
#include <iostream>
#include <map>
using namespace std;
map <int,int> mp;
int k,ca,vt[10000001];
bool pr[10000001]={1,1};
int main(){
cin.tie(0); ios::sync_with_stdio(false);
mp[0]=0;
for(int i=2;i<=3163;++i){
for(int j=i+i;j<=10000000;j+=i){
pr[j]=1;
}
}
for(int i=2,v=0;v<=10000000;++i){
int t=0;
if(pr[i]==0){
t=1;
}
else{
int tmp=i;
for(int j=2;tmp==i;++j){
if(tmp%j==0){
tmp/=j;
++t;
break;
}
}
t+=vt[tmp];
}
vt[i]=t;
v+=t;
mp[v]=i;
}
while(cin >> k){
if(k<0)break;
cout << "Case " << ++ca << ": ";
if(mp.find(k)==mp.end()){
cout << "Not possible.\n";
}
else{
cout << mp[k] << "!\n";
}
}
}