在一定的底数中找到整数的阶乘的位数 [英] Find the number of digit(s) of the factorial of an integer in a certain base

问题描述

我的解决方案非常快，但还不够.我需要更快.如何减少我的时间? 输入数字:n(0≤n≤1000000) 基数应为:基数(2≤基数≤1000)

My solution was pretty fast but not enough. I need more faster. How can I reduce my time? Input Number: n (0 ≤ n ≤ 1000000) Base should be: base (2 ≤ base ≤ 1000)

1. 输入5！在10个基地.输出为:3
2. 输入22！在3个基地.输出为:45

时间限制:2秒，内存限制:32 MB

Time Limit: 2 second(s), and Memory Limit: 32 MB

这是我用C语言编写的代码:

Here is my code in c language:

#include<stdio.h>
#include<math.h>
int factorialDigitExtended ( int n, int base ) {
    double x = 0;
    for ( int i = 1; i <= n; i++ ) {
        x += log10 ( i ) / log10(base);
    }
    int res = ( (int) x ) + 1;
    return res;
}

int main(){
    int i, t, n, b;
    for(i=1; i<= t; i++){
        scanf("%d %d", &n, &b);
        printf("Case %d: %d\n", i, factorialDigitExtended(n, b));
    }
    return 0;
}

推荐答案

就像我在上面的评论中提到的那样，这可能是针对特定目标的行为.我会看的几件事:

Like I mentioned in the comment above this might be target specific behavior. A few things I would look at:

仅计算一次常量值:

int factorialDigitExtended ( int n, int base ) {
    double x = 0;
    double lbase = log10(base);
    for ( int i = 1; i <= n; i++ ) {
        x += log10 ( i ) / lbase;
    }
    int res = ( (int) x ) + 1;
    return res;
}

划分可能很昂贵:

int factorialDigitExtended ( int n, int base ) {
    double x = 0;
    double lbase = 1 / log10(base);
    for ( int i = 1; i <= n; i++ ) {
        x += log10 ( i ) * lbase;
    }
    int res = ( (int) x ) + 1;
    return res;
}

不要重复相同的乘法n次:

Don't repeat the same multiplication n times:

int factorialDigitExtended ( int n, int base ) {
    double x = 0;
    double lbase = 1 / log10(base);
    for ( int i = 1; i <= n; i++ ) {
        x += log10 ( i );
    }
    x *= lbase;
    int res = ( (int) x ) + 1;
    return res;
}

0比较可能更便宜:

int factorialDigitExtended ( int n, int base ) {
    double x = 0;
    double lbase = 1 / log10(base);
    for ( int i = n; i > 0; --i ) {
        x += log10 ( i );
    }
    x *= lbase;
    int res = ( (int) x ) + 1;
    return res;
}

Btw(int)x可能由于精度问题而在某些时候失败.

Btw (int) x might fail at some points due to precision problems.

可能还会有处理器特定的对数指令.

There might also be processor specific logarithm instructions.

这篇关于在一定的底数中找到整数的阶乘的位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！