首页 > ACM题库 > HDU-杭电 > HDU 2940-Hex Factorial-高精度-[解题报告]HOJ
2014
02-24

HDU 2940-Hex Factorial-高精度-[解题报告]HOJ

Hex Factorial

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

1
15
-1

样例输出:

0
3

题意:求n的阶乘转为16进制后有多少个0

输入以负数结束,,n==0 时答案为0 

c++ 代码(二进制乘法)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;
const int M = 1009;
struct bt{
    int a[M];
    void init(){memset(a,0,sizeof(a));}
    void out()
    {
        for(int i=0;i<M;i++) cout<<a[i];cout<<endl;
    }
};
bt add(bt a,bt b)
{
    bt ans ;ans.init();
    int tmp = 0;
    for(int i=0;i<M;i++)
    {
        ans.a[i] = (a.a[i]+b.a[i]+tmp)%2;
        tmp = (a.a[i]+b.a[i]+tmp)/2;
    }
    return ans;
}
bt Multiply(bt a,bt b)
{
    bt tmp,ans;ans.init();
    for(int i=0;i<M;i++)
    if(a.a[i]==1)
    {
        tmp.init();
        for(int j=i;j<M;j++)
        tmp.a[j] = b.a[j-i];
        ans = add(ans,tmp);
    }
    return ans;
}
bt tobt(int k)
{
    bt ans;
    ans.init();
    for(int i=0;k;i++)
    ans.a[i]=k%2,k/=2;
    return ans;
}
int main()
{
    freopen("in.txt","r",stdin);
    int n;
    while(scanf("%d",&n)&&n>=0)
    {
        if(n==0)
        {
            printf("0\n");continue;
        }
        bt t ;
        t = tobt(1);
        for(int i=2;i<=n;i++)
        t = Multiply(t,tobt(i));//,t.out();
        int f,ans=0;
        for(int i=M-1;i>=0;i--)
        if(t.a[i])
        {
            f= i;
            break;
        }
        for(int i=0;i<=f;i+=4)
        if(!t.a[i]&&!t.a[i+1]&&!t.a[i+2]&&!t.a[i+3])
        ans++;
        printf("%d\n",ans);
    }
    return 0;
}

JAVA 大数

import java.math.*;
import java.util.*;
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin = new Scanner(System.in);
		
		while(true){
			BigInteger a = BigInteger.ONE;
			BigInteger si = BigInteger.valueOf(16);
		//BigInteger two = BigInteger.ONE.add(BigInteger.ONE);
			int n = cin.nextInt();
			if(n<0) break;
			if(n==0) {
				System.out.println(0); continue;
			}
			for(int i=2;i<=n;i++){
				a = a.multiply(BigInteger.valueOf(i));
			}
			//System.out.println(a);
			int ans = 0;
			while(a.max(BigInteger.ZERO).equals(BigInteger.ZERO)==false){
				//int t = 0;
				//for(int i=0;i<4;i++){
					if(a.mod(si).equals(BigInteger.ZERO)) ans++;
					//System.out.print(a.mod(si)+" ");
					a = a.divide(si);
			//	}
			//	if(t==0) ans++;
			}//System.out.println();
			System.out.println(ans);
		}
		cin.close();
	}

}

解题参考:http://blog.csdn.net/binwin20/article/details/7896716


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n