题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3621
题意描述:求k进制数n的阶乘的末尾有多少个0。
题目要求:k的范围:0<k<65,n的十进制数是__int64范围内的。

代码如下:
#include <stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 65
#define INF 0x7fffffffffffffff

int  prime[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
int cnt=18;
int kv[20];

//求进制数k的素因子
void K_Prime( int k ){
    int num,i;
    memset( kv, 0, sizeof(kv) );
    for( i=0; i<cnt; i++ ){
        num = 0;
        while( k%prime[i] == 0 ){
            num++;
            k = k/prime[i];
        }
        kv[i] = num;
    }
}
//求阶乘n的末尾有多少个0
void jiecheng( long long sum,int k ){
    long long i,num;
    long long min = INF,tmp;
    for(i=0; i<cnt; i++){
        tmp = sum;
        tmp /= prime[i];
        num = tmp;
        while( tmp ){
            tmp /= prime[i];
            num += tmp;
        }
        if( kv[i] && num/kv[i]<min )
            min = num/kv[i];
    }
    printf( "%lld\n",min );
}
//把k进制数n转化为十进制数
long long char_int( char s[],int k ){
    int len = strlen(s),i;
    long long sum = 0;
    for( i=0; i<len ; i++ ){
        if( s[i]>='0' && s[i]<='9' )
            sum = sum*k + (s[i]-'0');
        else if( s[i]>='A' && s[i]<='Z' )
            sum = sum*k + ( s[i]-'A' +10 );
        else
            sum = sum*k + ( s[i]-'a' + 36 );
    }
    return sum;
}

int main(){
    char s[150];
    int k;
    long long sum;
    while( scanf("%s%d", s, &k) != EOF ){
        K_Prime(k);
        sum = char_int( s,k );
        jiecheng( sum,k );
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation