Question

杭电ACM 1042 Wrong Answer？？？

N!
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 21788 Accepted Submission(s): 5798

Problem Description
Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

Input
One N in one line, process to the end of file.

Output
For each N, output N! in one line.

Sample Input
1
2
3

Sample Output
1
2
6

#include<stdio.h>
void main()
{
int n,i,s;
while(scanf("%d",&n)!=EOF){
s=n;
for(i=0;i<n-1;i++){
if(n==1)
printf("%d\n",s);
else{
s=s*(n-1);
n--;
}
}
}
}

Answer 1

13!=6227020800 已经超出int的范围了~，你现在10000！的阶乘~只能换高精度咯；
10000！ 是3万多位数了；

给我的AC代码你参考下~！

#include <iostream>
const int N=7300;

int main()
{
int m,n,k;
while(std::cin>>m)
{
int a[N+1]={0};
a[0]=1;
//------------------------------------------------------
for(n=2;n<=m;++n)
{
for(k=0;k<=N;++k)
a[k]*=n;
for(k=0;k<=N;++k)
{
if(a[k]>=100000)
{
a[k+1]+=a[k]/100000;
a[k]%=100000;
}
}
}
//-------------------------------------------------
for(k=N;!a[k];--k);
std::cout<<a[k];
for(--k;k>=0;--k)
printf("%05d",a[k]);
std::cout<<std::endl;
}
return 0;
}

Answer 2

10000! 必须溢出

追问

怎么改，为什么，谢谢

追答

改用高精度

#include
#include
#include
#define maxsize 8000
#define base 100000

typedef struct{
int x[maxsize],size;
} BigNumber;

void print(BigNumber* m){
int i;
int j;
i=m->size?m->size-1:0;
printf("%d",m->x[i]);
while(i--){
for(j=10;j*(m->x[i])x[i]);
}
}

BigNumber mul(BigNumber* m, int r)
{
int i=0,k=0;
BigNumber tmp;
memset(tmp.x,0,sizeof(tmp.x));
while(isize||k){
k+=m->x[i]*r;
tmp.x[i++]=k%base;
k/=base;
}
tmp.size=i;
return tmp;
}

int main()
{
int n,i;
BigNumber Num;
while(scanf("%d",&n)==1)
{
Num.size = 1;
memset(Num.x,0,sizeof(Num.x));
Num.x[0] = 1;
for(i=2;i<=n;i++)
{
Num = mul(&Num,i);
}
print(&Num);
printf("\n");
}
}