d419 - 00884 - Factorial Factors

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算 n! 的質因數分解後，所有質因數的指數總和。換句話說，我們要找出 n! 可以分解成多少個質因數的乘積（不包含 1）。

解題思路

這題的核心在於計算 n! 的質因數分解。我們可以利用質因數分解的性質，對於每個質數 p，計算 p 在 n! 中的指數。根據 Legendre's formula，p 在 n! 中的指數可以表示為 floor(n/p) + floor(n/p^2) + floor(n/p^3) + ...。

程式碼首先使用埃拉托斯特尼篩法找出 1100 以內的質數。然後，對於每個 i 從 2 到 1000000，計算 i! 的質因數分解指數總和。為了避免重複計算，程式碼使用動態規劃，ans[i] 儲存 i! 的質因數分解指數總和。ans[i] 的計算方式是 ans[i-1] 加上 i 的質因數分解指數總和。最後，程式讀取輸入的 n，並輸出 ans[n]。

複雜度分析

• 時間複雜度: O(N log log N + N * sqrt(N))，其中 N 是輸入的最大值 1000000。O(N log log N) 是篩選質數的複雜度，O(N * sqrt(N)) 是計算每個數字的質因數分解的複雜度。
• 空間複雜度: O(N + P)，其中 N 是輸入的最大值 1000000，P 是質數的數量（約為 184）。

程式碼

#include <iostream>
using namespace std;
int ans[1000005],n,p[200],sz;
bool isp[1505];
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	for(int i=2;i<=50;++i){
		for(int j=i+i;j<=1100;j+=i){
			isp[j]=1;
		}
	}
	for(int i=2;i<=1100;++i){
		if(isp[i]==0)p[sz++]=i;
	}
	for(int i=2;i<=1000000;++i){
		int tmp=i,ct=0;
		for(int j=0;p[j]*p[j]<=tmp;++j){
			while(tmp%p[j]==0){
				tmp/=p[j];
				++ct;
			}
		}
		if(tmp!=1)++ct;
		ans[i]+=ans[i-1]+ct;
	}
	while(cin >> n){
		cout << ans[n] << "\n";
	}
}