Finden Sie die Anzahl der Ziffer (n) des Faktors einer ganzen Zahl in einer bestimmten Basis

Question

Meine Lösung war ziemlich schnell, aber nicht genug. Ich brauche mehr schneller. Wie kann ich meine Zeit reduzieren? Eingangsnummer: N (0 ≤ n ≤ 1000000) Base sein sollte: Basis (2 ≤ Basis ≤ 1000)

1. Eingang 5! in 10 Basis. Ausgang ist: 3
2. Eingang 22! in 3 Basis. Die Ausgabe ist: 45

Zeitlimit: 2 Sekunden (s) und Memory Limit: 32 MB

Hier ist mein Code in C-Sprache:

---

#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

Zu allererst transformieren, können Sie:

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

zu:

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

Zweitens, können Sie wie folgt vorgehen:

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

Wie ich im Kommentar darüber erwähnt könnten spezifische Verhalten werden Ziel. Ein paar Dinge, die ich betrachten würde:

Nur konstante Werte berechnen einmal:

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

Abteilung kann teuer sein:

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

Sie niemals das gleiche Multiplikation n mal nicht wiederholen:

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 Vergleich könnte billiger sein:

Btw (int) x kann aufgrund von Präzisionsproblemen an einigen Punkten fehlschlagen.

Möglicherweise gibt es auch prozessorspezifische Logarithmusanweisungen.