E. Number With The Given Amount Of Divisors
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Given the number n, find the smallest positive integer which has exactly n divisors. It is guaranteed that for the given n 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.
Examples
Input
4
Output
6
Input
6
Output
12
思路:反素数;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define esp 0.00000000001
#define pi 4*atan(1)
const int N=1e5+,M=2e7+,inf=1e9+,mod=1e9+;
const ll INF=1e18;
int p[N]={,,,,,,,,,,,,,,,};
ll x;
ll num;
void dfs(int pos,ll ans,ll sum,int pre)
{
if(sum>x)return;
if(sum==x)
num=min(ans,num);
for(int i=;i<=pre;i++)
{
if(INF/ans<p[pos])break;
dfs(pos+,ans*=p[pos],sum*(i+),i);
}
}
int main()
{
scanf("%lld",&x);
num=INF;
dfs(,,,);
printf("%lld\n",num);
return ;
}