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

output

input

output

思路：反素数；

（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 }

巴特西

E. Number With The Given Amount Of Divisors

最新文章

热门文章