Codeforces 27 E. Number With The Given Amount Of Divisors

問題

正の整数nに対して、約数をちょうどn個だけ持つような最小の整数を求めよ。

制約条件

n≦1000
答えは10^18以下であることが保証されている。

方針

dp[i][j]を、素因数をi種類まで使ったときに約数の数がjであるときの整数の最小値とする。
すると、i+1種類目の素因数をいくつ使うかでdpテーブルが更新できる。


dp[i][n]の最小値が求める答えである。


O(n^2log(10^18))くらいの時間計算量であるが、
枝刈りがかなりされるので、高速に(最大ケースで30msくらいで)動く。

ソースコード

int n;
ll dp[1001][1001];
bool p[10000];
void run()
{
	cin>>n;
	memset(p,0,sizeof(p));
	vi prime;
	for(int i=2;i*i<10000;i++)if(!p[i]){
		prime.pb(i);
		for(int j=i*i;j<10000;j+=i)p[j]=1;
	}
	
	rep(i,n+1)rep(j,n+1)dp[i][j]=1ll<<60;
	dp[0][1]=1;
	ll ans=1ll<<60;
	rep(i,n)rep(j,n)if(dp[i][j]!=1ll<<60){
		ll tmp=dp[i][j];
		for(int k=2;k*j<=n;k++){
			tmp*=prime[i];
			if(tmp>1ll<<60)break;
			dp[i+1][j*k]=min(dp[i+1][j*k],tmp);
		}
	}
	rep(i,n+1)ans=min(ans,dp[i][n]);
	cout<<ans<<endl;
}