Eulero 160: trova le 5 cifre non banali del fattoriale

Dato un numero, trova le 5 cifre prima dello zero finale. 9! = 362880 così f (9) = 36288 10! = 3628800 so f (10) = 36288 20! = 2432902008176640000 quindi f (20) = 17664 Find f (1.000.000.000.000)Eulero 160: trova le 5 cifre non banali del fattoriale

Per questo ho calcolato il f(10^6) e poi f(10^12) = (f(10^6))^(10^6) per il calcolo del f(n) ... Sto calcolando la fattoriale, eliminando qualsiasi 5 e il corrispondente 2 in modo da rimuovere tutti gli zeri finali .
Ma ho una risposta sbagliata.
C'è un problema nell'approccio o qualche errore stupido?

codice di riferimento

long long po(long long n, long long m, long long mod) { 
    if (m == 0) return 1; 
    if (m == 1) return n % mod; 
    long long r = po(n, m/2, mod) % mod; 
    if (m % 2 == 0) return (r * r) % mod; 
    return (((r * r) % mod) * n) % mod; 
} 

void foo() { 
    unsigned long long i, res = 1, m = 1000000 , c = 0, j, res1 = 1, mod; 
    mod = ceil(pow(10, 9)); 
    cout << mod << endl; 
    long long a = 0, a2 = 0, a5 = 0; 
    for (i = 1 ; i <= m; i++) { 
     j = i; 
     while (j % 10 == 0) 
      j /= 10; 
     while (j % 2 == 0) { 
      j /= 2; 
      a2++; 
     } 
     while (j % 5 == 0) { 
      j /= 5; 
      a5++; 
     } 
     res = (res * j) % mod; 
    } 

    a = a2 - a5; 

    for (i = 1; i <= a; i++) 
     res = (res * 2) % mod; 
    for (i = 1; i <= 1000000; i++) { 
     res1 = (res1 * res) % mod; 
    } 
    cout << res1 << endl; 
}

fonte

2012-02-17 titan

Puoi pubblicare il tuo codice? – 0605002

inoltre, non è un progetto euler qualcosa che dovresti risolvere da solo piuttosto che chiedere aiuto ... solo dicendo se lasci che qualcun altro lo risolva per te, non solo non otterrai nulla da esso ma anche la risposta sarà ora su COSÌ, per tutti da vedere. – hackartist

tuo uguaglianza f(10^12) = (f(10^6))^(10^6) è sbagliato. f() è basato su fattoriali, non su potenze.

fonte

2012-02-17 18:57:55

La mia ipotesi: abbiamo calcolato le ultime 5 cifre di (10^6)! ora tutte le altre cifre> 10^6 avranno le stesse 5 cifre finali usando le quali abbiamo calcolato il (10^6)! Quindi f (2 * (10^6)) = f (10^6)! * f (10^6) In modo simile f (n * 10^6) = (f (10^6))^n – titan

@titan: ma gli zeri finali nei numeri significano che non è possibile trattare l'intero modulo problema 1000000 così. Ad esempio, 123000 nel tuo primo milione contribuiranno con cifre diverse rispetto a 5 rispetto a 1123000, quindi non sono equivalenti. –

tue ipotesi sono errate:

f (10^12) non è la stessa f (10^6)^(10^6).
al fine di ottenere il numero basso di 0 cifre del fattoriale, non è sufficiente rimuovere tutti i multipli di 10, 2 e 5 dai moltiplicativi. Rimozione dei multipli di 10 è una buona idea, per 5 e 2, è necessario rimuovere il fattore 2 o 5 solo se l'altro multiplo è un multiplo di 5 e 2 rispettivamente.

Si dovrebbe semplificare il codice e calcolare modulo certa potenza di 10, ma 10^9 sembra troppo alto 10^9 * 10^12 traboccherà 64 bit di tipo unsigned long long.

fonte

2017-02-13 20:29:24 chqrlie

Eulero 160: trova le 5 cifre non banali del fattoriale

risposta

Problemi correlati