UVa 10061 多少个零和数字？

/*

* 解题思路：

* 久违的一道不水的题,相当于两个问题，一个是求后缀0有多少个,一个是求数字有多少位

* 后者较容易,直接用取对数及换底公式即可,

* 前者就要拐拐弯了、我的做法是，首先先打素数表,( 因为任何一个合数都可以由素数组成 ),

* 只要存在多个素数相乘的积为 进制B ， 则末位出现一个0,重复该操作直到最后无法提供足够素数使得到 B值即跳出循环即可~

*/

#include 
  
   
#include 
   
     #include 
    
      int N,B,sumZ,sumD; int prime[ 1048576 ]; void SumDigit( ) { int i; double sum=0; for( i=2;i<=N;i++ ) sum += log10( i ); sumD = floor( sum/log10( B ) + 1e-9 ) + 1; } void SumZero( ) { int i,j,k,tmp; for( i=2;i<=N;i++ ) if( !prime[ i ] ) { prime[ i ]++; for( j=i+i;j<=N;j+=i ) { prime[ j ] = -1; tmp = j; while( tmp % i == 0 ) { tmp/=i; prime[ i ]++; } } } for( i=2,k=B;i<=N && i<=B ;i++ ) { while( k%i==0 && prime[ i ]>0 ) { prime[ i ]--; k /= i; if( k==1 ) { i=2; k=B; sumZ++; } } } } int main( ) { while( ~scanf("%d%d",&N,&B) ) { memset( prime , 0 , sizeof( prime ) ); sumD = sumZ = 0; SumZero( ); SumDigit( ); printf("%d %d\n",sumZ,sumD); } return 0; }