Hex Factorial

Time limit2000ms Memory limit 32768kB

高精度

来源：
HDU 2940 Hex Factorial
vjudge A Hex Factorial

Description

The expression N!, reads as the factorial of N, denoting the product of the first N positive integers. If the factorial of N is written in hexadecimal without leading zeros, can you tell us how many zeros are there in it? Take 15! as an example, you should answer "3" because (15)10! = (13077775800)16, and there are 3 zeros in it.

Input

The input contains several cases. Each case has one line containing a non-negative decimal integer N (N ≤ 100). You need to count the zeros in N! in hexadecimal. A negative number terminates the input.

Output

For each non-negative integer N, output one line containing exactly one integer, indicating the number of zeros in N!.

Sample Input

1
15
-1

Sample Output

0
3

题意：

该题目的为求某数的阶乘后再将其转换为16进制数，问其16进制数中有多少个0。
多组输入，输入一个数，输出0的个数，当输入负数时结束！
大数的进制转换：一直除以该数，当商为0时结束，转换结果为每次所得的余数。

完整代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int a[160],b[160],s[160];///10!的位数未超过160。
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n<0)///注意！！！当n<0的时候都要结束！！！
         break;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(s,0,sizeof(s));
        a[0]=1;
        int num=1;
        int t;
        ///计算n的阶乘！！！
        for(int i=1;i<=n;i++)
        {
            int temp=0;///进位！
            for(int j=0;j<num;j++)
            {
                t=i*a[j]+temp;
                a[j]=t%10;
                temp=t/10;
            }
            while(temp)
            {
                a[num]=temp%10;
                num++;
                temp/=10;
            }
        }
        ///去前导零
         for(int i=num;i>0;i--)
         {
             if(a[i]==0)
                num--;
             else
                break;
         }
         /*printf("10jz:\n");
         for(int i=num;i>=0;i--)
            printf("%d",a[i]);
         printf("\n");*/
         ///将高精度10进制数转为16进制！！
         int j=0;
         while(a[num]>0)
         {
             t=0;
             for(int i=num;i>=0;i--)
             {
                t=t*10+a[i];
                a[i]=t/16;
                t%=16;
                if(i==0)
                    s[j]=t;
            }
            for(int i=num;i>=0;i--)
            {
                if(a[i]==0)
                    num--;
                else
                    break;
            }
            j++;
         }
         //printf("%d#\n",j);
        /*printf("16jz:\n");
         for(int i=j-1;i>=0;i--)
            printf("%d",s[i]);
         printf("\n");*/
         ///计算0的个数
         int count=0;
         for(int i=j-1;i>=0;i--)
         {
             if(s[i]==0)
                count++;
         }
         printf("%d\n",count);
    }
    return 0;
}