首页 > 代码库 > Just the Facts UVA 568

Just the Facts UVA 568

说说:这道题的题意是求出给定的N!(N<=10000)的第一个非零的数。可以想象10000!是非常可怕的,所以我开始的想法是将1~10000的结果都求出来保存在数组中,然后直接调用即可。而求结果的方法是从1开始键乘,且只保存结果的最后非零的两位。因为在很多情况下,第一个非零的数与太后面的数是没什么关系的。按照这个思路测试了一下,发现比较小的数没问题,当N逐渐变大的时候,后面就全乱了。原因应该是暂存的结果再乘以新的N的时候前两位就是0,所以最后的结果其实是与暂存结果的第三位数有关的,因此结果至少要保留三位。但是三位还是有问题,最后要保留5位才水过去了.....具体是在哪个数会出现连续后面产生四个零,我也不知道。希望有哪位大神知道的指导下!(*^__^*) 嘻嘻……



题目:

Just the Facts

The expression N!, read as ``N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, forexample,,表达式N!读作N的键乘,意思是前N个正整数的乘机。所以,例如:

NN!
01
11
22
36
424
5120
103628800

For this problem, you are to write a program that can compute the last non-zero digit of any factorial for ( $0 \le N \le 10000$). For

现在你要写个程序计算出(0<=N<=10000)N!的第一个非零的数字位。

 example, if your program is asked to compute the last nonzero digit of 5!, your program should produce ``2" because 5! = 120, and 2 is

例如,计算5!的第一个非零数字,你的程序应当输出“2”因为5!=120,并且2是120的第一个非零的数字

 the last nonzero digit of 120.

Input

Input to the program is a series of nonnegative integers not exceeding 10000, each on its own line with no other letters, digits or spaces.

程序的输入是一系列不超过10000的非负整数,每个整数一行且没有多余的字母,数字或空格

 For each integer N, you should read the value and compute the last nonzero digit of N!.

对于每个整数N,你需要读取并计算N!的第一个非零数位

Output

For each integer input, the program should print exactly one line of output. Each line of output should contain the value N, right-justified

对于每个输入整数,程序需要输出一行。输出的每行包括N,在1~5列的范围内右对齐,不足的用空格补齐

 in columns 1 through 5 with leading blanks, not leading zeroes. Columns 6 - 9 must contain `` -> " (space hyphen greater space).

第6~9列输出“ -> ”

 Column 10 must contain the single last non-zero digit of N!.

第十行输出N!的第一个非零数位

Sample Input

1
2
26
125
3125
9999

Sample Output

    1 -> 1
    2 -> 2
   26 -> 4
  125 -> 8
 3125 -> 2
 9999 -> 8


源代码:

#include <stdio.h>
#define MAXN 10000+5

char ans[MAXN];
void produce_ans(void);//求出0~MAXN范围内的答案
int main(){
  int N;
  //freopen("input.txt","r",stdin);
  produce_ans();
  while(~scanf("%d",&N))
    printf("%5d -> %d\n",N,ans[N]);

  return 0;
}

void produce_ans(){
  int i,temp;
  ans[0]=1;
  temp=1;

  for(i=1;i<=MAXN;i++){
    temp*=i;
    while(temp%10==0)
        temp/=10;

    temp=temp%100000;//保存5位数字
    ans[i]=temp%10;
  }
}