acm 数学题(Highly Composite Number)

发布网友 发布时间：2024-10-23 05:20

我来回答

共1个回答

热心网友 时间：2024-11-19 21:47

想了我很久啊~~ 首先，有一个关系，第n大的Highly Composite Number，由前n-1大的Highly Composite Number乘以一个质数得到的。由于，仅求前45个，大胆地仅使用前10个质数即可。
初始化为2，仅1个质因子，因子数为2
然后每遇到一个数的因子数比现在的因子数大，那这个数就是所求的下个Highly Composite Number，然后由这个数各自乘以前10个质数，再压回去堆里面。知道找到前45个。详细看代码。
#include<iostream>
#include<queue>
using namespace std;
struct node
{
int fa[10];
int f;
int num;
};
int zs[]={2,3,5,7,11,13,17,19,23,29};
priority_queue<node> q;
bool operator <(node a,node b)
{
if(a.num!=b.num) return a.num>b.num;
else return a.f>b.f;
}
int ans[50];
int al;
void deal(node &a)
{
int i;
a.f=1;
for(i=0;i<10;i++) a.f*=a.fa[i]+1;
}
void init()
{
node temp,new_one;
int i,j;
for(i=0;i<10;i++) temp.fa[i]=0;
temp.fa[0]=1;
deal(temp);
temp.num=2;
q.push(temp);
al=1;
int now_f=0;
while(al<=46)
{
temp=q.top();
q.pop();
if(temp.f>now_f)
{
now_f=temp.f;
ans[al++]=temp.num;
for(i=0;i<10;i++)
{
temp.fa[i]++;
temp.num*=zs[i];
deal(temp);
q.push(temp);
temp.fa[i]--;
temp.num/=zs[i];
}
}
}
}
int main()
{
init();
int n;
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",ans[n]);
}
return 0;
}