题目描述
对于任意输入的正整数n，请编程求出具有n个不同因子的最小正整数m。例如：n=4，则m=6，因为6有4个不同整数因子1，2，3，6；而且是最小的有4个因子的整数。
输入输出格式 输入格式：n（1<=n<=50000）
输出格式：
m
对于m=a1^p1 * a2^p2 * … * an^pn，因数个数为(p1+1) * (p2+1) * … * (pn+1)，所以只需要枚举每个因数的次数。又因为要求最小，所以从大到小质因数的个数一定单调不增。这样搜索就很快了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int mod=10000,maxl=3000;
struct big
{int a[maxl+10],l;bool operator < (const big & b) const{if (l!=b.l) return l<b.l;for (int i=l;i;i--)if (a[i]!=b.a[i])return a[i]<b.a[i];return 0;}big operator * (const int &x) const{big ret;ret.a[1]=0;for (int i=1;i<=l;i++){ret.a[i]+=a[i]*x%mod;ret.a[i+1]=a[i]*x/mod;}if (ret.a[l+1]) ret.l=l+1;else ret.l=l;return ret;}
}one,oo;
int n,prm[]={
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
big ans;
void dfs(int p,big x,int lim,int now)
{int i;if (ans<x) return;if (now==n){ans=x;return;}for (i=1,x=x*prm[p];i<=lim&&now*(i+1)<=n&&x<ans;i++,x=x*prm[p])dfs(p+1,x,i,now*(i+1));
}
int main()
{int i,j,k,p,q,x,y,z;scanf("%d",&n);oo.l=maxl;for (i=1;i<=maxl;i++)oo.a[i]=mod-1;one.l=one.a[1]=1;ans=oo;dfs(0,one,0x3f3f3f3f,1);printf("%d",ans.a[ans.l]);for (i=ans.l-1;i;i--){x=ans.a[i];if (x<1000) printf("0");if (x<100) printf("0");if (x<10) printf("0");printf("%d",x);}printf("\n");
}