2014
02-24

# 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

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 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];
}
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);
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();
}

}

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