hdu 1042 N！ 高精度问题

N!

Time Limit: 10000/5000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 27897Accepted Submission(s): 7646

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

典型的高精度问题。本来昨晚就做了一下，但悲催的TLE了，尝试多次无果。今晚查了点资料 。终于AC了。思路在代码中。先贴之前TLE的低效代码。

#include<stdio.h>
#include<string.h>
#define MAXN 50000
int a[MAXN];
int main()
{
    int n,i,j,temp;
    while(scanf("%d",&n)!=EOF)
    {
        memset(a,0,sizeof(a));
        a[0]=1;
        for(i=2;i<=n;i++)
        {
            temp=0;
            for(j=0;j<MAXN;j++)            //此处多了很多没必要的运算。 
            {
                int s=a[j]*i+temp;         //下面大数相乘的过程还是没错的。temp是进位的数。
                a[j]=s%10;
                temp=s/10;
            }
        }
        for(j=MAXN-1;j>=0;j--) if(a[j]) break;
        for(i=j;i>=0;i--) printf("%d",a[i]);
        putchar('\n');
    }
    return 0;
}

下面是改进的代码

#include<stdio.h>
#include<string.h>
#define MAXN 50000
int a[MAXN];
int main()
{
    int n,i,j,temp;             //这道题思路就就是把大数用数组存储。然后模拟乘法运算
    while(scanf("%d",&n)!=EOF)
    {
		int digit=1;      //改进之处：定义了一个digit变量 记录数位。
        memset(a,0,sizeof(a));
        a[0]=1;
        for(i=2;i<=n;i++)
        {
            temp=0;
            for(j=0;j<digit;j++)
	    {
                int s=a[j]*i+temp;
                a[j]=s%10;
                temp=s/10;
            }
            while(temp)                //把进位的数字存入数组 ，同时记下了数的位数。
	    {
		a[digit++]=temp%10;
		temp/=10;
	    }
        }
        for(i=digit-1;i>=0;i--) printf("%d",a[i]);
        putchar('\n');
    }
    return 0;
}

这题还有改进的空间。 下次再修改。

今晚其实有点亢奋，精神正好。 但还是睡吧 ，不然明天老妈又要 ψ(╰_╯) 了 哈哈。such a wonderful night。 睡觉。