toj_2845.cpp

Tianjin University Online Judge 的80多道题目 .

/*2845.   Factorial Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 387   Accepted Runs: 136


Robby is a clever boy, he can do multiplication very quickly, even in base-2 (binary system), base-16 (hexadecimal system) or base-100000.

Now he wants to challenge your computer, the task is quite simple: Given a positive integer N, if we express the N ! (N ! = N * (N - 1) * (N - 2) * ... * 2 * 1) in base-B, how many ZEROs there will be at the end of the number. Can you make a wonderful program to beat him?

Input
Each test case contain one line with two numbers N and B. (1 ≤ N ≤ 109, 2 ≤ B ≤ 100000)

The input is terminated with N = B = 0.
Output
Output one line for each test case, indicating the number of ZEROs.
Sample Input

7 10
7 10000
7 2
0 0

Sample Output

1
0
4

Hint
7! = (5040)10, so there will be one zero at the end in base-10. But in base-10000, the number (5040)10 can be expressed in one non-zero digit, so the second answer is 0. In base-2, 7! = (1001110110000)2, so the third answer is 4.

Problem Setter: RoBa



Source: Tianjin Metropolitan Collegiate Programming Contest 2007*/
#include<cstdio>
#include<cstring>
int const MAX = 100010;

void generatePrime( char prime[] )
{
  int i , j , k;
  memset( prime , 1 , MAX );
  for ( i = 2; i < MAX; i++ )
    {
      if ( prime[ i ] )
	for ( j = 2 * i; j < MAX; j += i )
	  prime[ j ] = 0;
    }
}
	  
int main()
{
  char prime[ MAX ];
  int factor[ MAX / 100 ][ 3 ];
  int n , nCopy , b , i , j , k , nOfFactor , min;
  generatePrime( prime );
 /* for ( i = 0; i < MAX; i++ )
    if ( prime[ i ] )
      printf( "%d " , i );
  printf( "\n" );*/
  while ( scanf( "%d%d" , &n , &b ) != EOF && n != 0 && b != 0 )
    {
      nOfFactor = 0;
      memset( factor , 0 , 3 * sizeof( int ) * MAX / 100 );
      for ( i = 2; i <= b; i++ )
	{
	  if ( b % i == 0 && prime[ i ] )
	    {
	      factor[ nOfFactor ][ 0 ] = i;
	      while ( b % i == 0 )
		{
		  b /= i;
		  factor[ nOfFactor ][ 1 ]++;
		}
	      nOfFactor++;
	    }
	}
      for( i = 0; i < nOfFactor; i++ )
	{
	  nCopy = n;
	  while ( nCopy != 0 )
	    {
	      nCopy /= factor[ i ][ 0 ];
	      factor[ i ][ 2 ] += nCopy;
	    }
	  factor[ i ][ 2 ] /= factor[ i ][ 1 ];
	}
      min = MAX;
/*      for ( i = 0; i < nOfFactor; i++ )
	{
	  printf( "%d %d %d\n" , factor[ i ][ 0 ] , factor[ i ][ 1 ] , factor[ i ][ 2 ] );
	}
  */
      for ( i = 0; i < nOfFactor; i++ )
	if ( factor[ i ][ 2 ] < min )
	  min = factor[ i ][ 2 ];
      printf( "%d\n" , min );
    }
  return 0;
}