Codeforces Beta Round #27 (Codeforces format, Div. 2) E. Number With The Given Amount Of Divisors 反素数

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 ;
}
上一篇:购物车数字加减按钮HTML+CSS+JS(有需要嫌麻烦的小伙伴拿走不谢)


下一篇:jQuery数字加减插件