1825.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"iostream.h"
#include"memory.h"
int x[20],y[20],m;
int s[2000],len;
void cheng(int a)
{int i,t;
for(i=0,t=0;i<len;i++)
{s[i]*=a;s[i]+=t;
t=s[i]/10;
s[i]%=10;
}
while(t)
{s[len++]=t%10;
t/=10;
}

}
int p[]={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,
     101,     103   ,  107,     109  ,   113,
     127 ,    131  ,   137 ,    139 ,    149 ,    151 ,    157    , 163 ,    167     ,173,
     179  ,   181 ,    191  ,   193,     197  ,   199,     211   ,  223  ,   227    , 229,
     233   ,  239,     241   }  ,z[300];

void init()
{int i,j;
cin>>m;
for(i=0;i<m;i++)cin>>y[i];
for(i=0;i<y[0];i++)
{for(j=0;j<m&&y[j]>i;j++);
x[i]=j;
}

}
inline int find(int i,int j)
{return (y[i]+x[j]-i-1-j-1+1);
}

void doit()
{int d=0,k;
int i,j,n=sizeof(p)/sizeof(int);
for(i=0;i<m;i++)d+=y[i];
for(i=0;i<n;i++)z[i]=0;
for(i=0;d>=0;i++,d--)
{k=d;
for(j=0;j<n&&k>1;j++)
if(k%p[j]==0){z[j]++;k/=p[j];j--;}
}
int l;
len=1;s[0]=1;
for(i=0;i<m;i++)
for(j=0;j<y[i];j++)
{k=find(i,j);
for(l=0;l<n&&k>1;l++)
if(k%p[l]==0){z[l]--;k/=p[l];l--;}
}
//_int64 s=1;
for(i=0;i<n;i++)
{
	while(z[i])
	{cheng(p[i]);z[i]--;}
}
for(i=len-1;i>=0;i--)
printf("%d",s[i]);
printf("\n");
}
int main()
{init();
doit();
return 0;
}