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
思路：反素数；
（1）一个反素数的所有质因子必然是从2开始的连续若干个质数，因为反素数是保证约数个数为的这个数
尽量小
（2）同样的道理，如果，那么必有
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string.h>
5 #include<queue>
6 #include<math.h>
7 #include<set>
8 #include<vector>
9 #include<string.h>
10 using namespace std;
11 typedef long long LL;
12 bool prime[100];
13 int ans[100];
14 LL minn = 1e18+10;
15 LL maxx = 1e18;
16 void dfs(LL n,int cn,int pre,int need,int cnt);
17 int main(void)
18 {
19 LL m,n;
20 int i,j;
21 int cn = 0;
22 memset(prime,0,sizeof(prime));
23 for(i = 2 ; i < 100 ; i++)
24 {
25 if(!prime[i])
26 {
27 ans[cn++] = i;
28 for(j = i; (i*j) <= 100 ; j++)
29 {
30 prime[i*j]=true;
31 }
32 }
33 }
34 int ak = 16;
35 while(scanf("%lld",&n)!=EOF)
36 {
37 minn = 1e18+10;
38 dfs(1,0,63,n,1);
39 printf("%lld\n",minn);
40 }
41 return 0;
42 }
43 void dfs(LL n,int cn,int pre,int need,int cnt)
44 {
45 if(cnt>need)return ;
46 if(cnt == need)
47 {
48 minn = min(minn,n);
49 return ;
50 }
51 LL ap = 1;
52 int i,j;
53 for(i = 1; i <= pre; i++)
54 { if(maxx/ap>=ans[cn])
55 ap*=ans[cn];
56 else return ;
57 if(maxx/n >= ap)dfs(n*ap,cn+1,pre,need,cnt*(1+i));
58 else return ;
59
60 }
61 }