E - Number With The Given Amount Of Divisors
Crawling in process...Crawling failedTime
Limit:2000MSMemory Limit:262144KB
64bit IO Format:%I64d & %I64u
Description
Given the number n, find the smallest positive integer which has exactlyn divisors. It is guaranteed that for the givenn the answer will
not exceed 1018.
Input
The first line of the input contains integer n (1 ≤ n ≤ 1000).
Output
Output the smallest positive integer with exactly n divisors.
Sample Input
Input
4
Output
6
Input
6
Output
12
思路：枚举，2^64会爆，所以最多枚举到64，一个数的因子数为（p1+1）*（P2+1）...
#include<iostream>
#include<cstring>
using namespace std;
const long long oo=1000000000000000009;
const int p[]={2,3,5,7,11,13,17,19,23,29};
int n;
long long ans;
void dfs(int dep,long long tmp,int x)
{ if(dep>n)return;
if(dep==n&&ans>tmp){ans=tmp;return;}
for(int i=1;i<=64;i++)///最多，2^64会爆
{ if(ans/p[x]<tmp)break;
dfs(dep*(i+1),tmp*=p[x],x+1);
}
}
int main()
{
while(cin>>n)
{
ans=oo;
dfs(1,1,0);
cout<<ans<<"\n";
}
}