UVa 11960

題目

http://domen111.github.io/UVa-Easy-Viewer/?11960

多筆測資，每筆測資包含一個正整數 $X$ ，求所有 $<=X$ 的正整數當中，因數個數最多的最大整數為何

想法

先做質因數分解，並且透過以下的想法可以找出每個數的因數個數

我們可以觀察 $24 = 2^3 * 3$

其中的因數包含了 $1, 2, 3, 4, 6, 8, 12, 24$

觀察一下會發現，這些因數都是由 $2$ 的某個小餘等於 $3$ 的次方乘上 $3$ 的某個小於等於 $1$ 的次方組合而成

也就是說我可以選擇要拿多少 $2$ 以及要拿多少 $3$ ，因數個數為 $(3+1)*(1+1)=8$

所以我們得到若 $X=a^p+b^q+c^r$ ，則 $X$ 的因數個數為 $(p-1)(q-1)(r-1)$

話說回來，利用上述的性質，加上質因數分解，就可以輕鬆求出每個數值的因數個數

而由於題目只需要所有 $<=X$ 的正整數當中，因數個數最多的最大整數，所以我們可以預先處理好所有人的答案

Code

//By Koios1143
#include<iostream>
const int MaxN = 1e6+5;
int fact[MaxN],ans[MaxN];
using namespace std;
int t,x;
int main(){
	for(long long i=2 ; i<=MaxN ; i++){
		if(!fact[i]){
			fact[i]=i;
			for(long long j=i*i ; j<=MaxN ; j+=i){
				if(!fact[j]){
					fact[j]=i;
				}
			}
		}
	}
	
	for(int i=1 ; i<=MaxN ; i++){
		// 後面要做乘法，所以預設值為 1
		ans[i]=1;
	}
	for(int i=2 ; i<=MaxN ; i++){
		int tmp=i;
		while(tmp!=1){
			int p=fact[tmp], cnt=0;
			while(tmp%p==0){
				tmp/=fact[tmp];
				cnt++;
			}
			ans[i]*=(cnt+1);
		}
	}
	
	// 預處理答案
	int n=2,m=ans[2];
	for(int i=2 ; i<=MaxN ; i++){
		if(ans[i]>=m){
			m=ans[i];
			n=i;
		}
		ans[i]=n;
	}
	
	cin>>t;
	while(t--){
		cin>>x;
		cout<<ans[x]<<"\n";
	}
	return 0;
}

複雜度分析

質數篩的複雜度為 $O(NloglogN)$

對所有數值做質因數分解，時間複雜度約為 $O(Nlog\Omega(X))$

預處理答案的時間複雜度為 $O(N)$

每筆回答時間複雜度為 $O(1)$

總時間複雜度為 $O(NloglogN + Nlog\Omega(X) + O(N) + O(t))$