【codeforces 27 E】【反素数】【给一个数n，求一个最小的正整数，使得它的因子个数为n】

传送门：http://codeforces.com/problemset/problem/27/E

描述;

E. Number With The Given Amount Of Divisorstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Given the number n, find the smallest positive integer which has exactly n 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.

Examplesinput

4

output

6

input

6

output

12

题意：

给一个数n，求一个最小的正整数，使得它的因子个数为n

思路：

与求因子的方法类似，先建立搜索树，以每一个pi为一层建立树型结构，进行搜索，取最小的。

反素数的讲解：点击打开链接

代码：

#include <bits/stdc++.h>
using  namespace  std;
#define ull unsigned long long

const ull inf = ~0ULL;

int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};//这16个素数乘起来接近于ull最大值 
//因为质因数的指数不递减，所以所以指数为1的时候不爆ull的最多16个质数
int n;
ull ans;

void dfs(int dep, ull tmp, int num){
  //深度，当前数的值，因数的个数
  if(num > n)return ;//因数多于n回溯
  if(num == n && ans > tmp) ans = tmp;
  for(int i = 1; i <= 63; i++){ //枚举指数
    if(tmp  > ans / p[dep])break; //满足最小
    dfs(dep + 1, tmp *= p[dep], num * (i + 1));
  } 
}

int  main(){
  while(cin>>n){
    ans = inf;
    dfs(0, 1, 1);
    cout << ans << endl;
  }
  return 0;
}