Найти число цифр факториала целого числа в определенной базе

Question

Мое решение было довольно быстрым, но недостаточно. Мне нужно быстрее. Как я могу сократить свое время? Входной номер: N (0 ≤ N ≤ 1000000) Основание должно быть: основание (2 ≤ ≤ база 1000)

1. вход 5! в 10 базах. Выход: 3
2. Вход 22! в 3 базах. Выход: 45

Лимит времени: 2 секунд (ы), и Лимит памяти: 32 MB

Вот мой код в языке Си:

---

#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; 
} 

Answer 1

Прежде всего , вы можете преобразовать:

for (int i = 1; i <= n; i++) { 
    x += log10(i)/log10(base); 
} 

к:

for (int i = 1; i <= n; i++) 
    x += log10(i); 
x /= log10(base); 

Во-вторых, вы можете делать так:

double x; 
int i, p; 

x = 0; 
for (i = 1; i <= n;) { 
    for (p = i++; i <= n && p < p * i; ++i) 
     p *= i; 
    x += log10(p); 
} 
x /= log10(base); 

Answer 2

Как я уже говорил в комментарии выше, это может быть цель конкретного поведения. Несколько вещей, которые я хотел бы посмотреть на:

только вычислить постоянные значения сразу:

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; 
} 

Не повторить тот же умножение п раз:

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 может быть неисправен в некоторых точках из-за проблем с точностью.

Также могут быть специальные инструкции для логарифма процессора.