http://codeforces.com/problemset/problem/27/E

RT，求含n个约数的最小的数

我们设答案p = 2^t1 * 3^t2 * …… * p^tk（其中p是第k大的质数），则必有：t1 >= t2 >= t3 >= … >= tk >= 0。

反证法证明：若不然可将{ti}由大到小排序，设形成的新有序序列是{ti’}，t1' >= t2' >= t3' >= … >= tk'；令p’ = 2^t1' * 3^t2' * …… * p^tk'，则：p' < p，但p'的约数个数却不少于p，矛盾。所以必有：t1 >= t2 >= t3 >= … >= tk。

然后就是dfs可搞，传递三个参数：构造的t序列长度，构造出的数的约数的个数，构造出的数的大小。

ULL可做

#pragma comment(linker, "/STACK:36777216")

#pragma GCC optimize ("O2")

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <map>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define clr0(x) memset(x,0,sizeof(x))

#define eps 1e-9

const double pi = acos(-1.0);

typedef long long LL;

typedef unsigned long long ULL;

const int modo = 1e9 + 7;

const int INF = 0x3f3f3f3f;

const int maxn = 1005,maxm = 1e4 + 5;

int n,pr[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

ULL ans = ~0ULL;

void dfs(int dep,int cnt,ULL res)

{

if(cnt > n)

return;

if(cnt == n){

ans = min(ans,res);

return ;

}

for(int i = 1;i <= 63;++i){

if(res > ans/pr[dep])

break;

dfs(dep+1,cnt*(i+1),res *= pr[dep]);

}

}

int main(){

RD(n);

dfs(0,1,1);

printf("%I64d\n",ans);

return 0;

}

LL可做

#pragma comment(linker, "/STACK:36777216")

#pragma GCC optimize ("O2")

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <map>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define clr0(x) memset(x,0,sizeof(x))

#define eps 1e-9

const double pi = acos(-1.0);

typedef long long LL;

typedef unsigned long long ULL;

const int modo = 1e9 + 7;

const int INF = 0x3f3f3f3f;

const int maxn = 1005,maxm = 1e4 + 5;

int n,pr[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

LL ans = 1e18;

void dfs(int dep,int cnt,LL res)

{

    if(cnt > n)

        return;

    if(cnt == n){

        ans = min(ans,res);

        return ;

    }

    for(int i = 1;i <= 63;++i){

        if(res > ans/pr[dep])

            break;

        dfs(dep+1,cnt*(i+1),res *= pr[dep]);

    }

}

int main(){

    RD(n);

    dfs(0,1,1);

    printf("%I64d\n",ans);

    return 0;

}