CF27E：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

题意：给出n，输出最小的有n个因子的数。

思路：深搜答案，2^64就超过1018了，每个数枚举64次即可。

# include <iostream> # define ULL unsigned long long using namespace std; int n, p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; ULL ans; void dfs(int depth, ULL tmp, int num) { if(num > n || depth >= 16) return; if(num == n && tmp < ans) ans = tmp; for(int i=1; i<=64; ++i) { if(ans < tmp) break; dfs(depth+1, tmp *= p[depth], num*(i+1)); } } int main() { while(cin >> n) { ans = ~0ULL; dfs(0, 1, 1); cout << ans << endl; } return 0; }