Come usare Modulo in modo efficiente?

Question

Sto facendo un'attività (per me stesso) molto complessa, in cui devo calcolare il maggior numero possibile di sequenze quando viene dato un numero n di segmenti.

Ho scoperto che il numero in catalano rappresenta queste sequenze e ho funzionato per n < = 32. I risultati che ottengo dovrebbero essere calcolati mod 1.000.000.007. Il problema che ho è che "q" e "p" diventano grandi per un lungo int lungo e non posso semplicemente mod 1.000.000.007 prima di dividere "q" e "p" perché otterrei un risultato diverso.

La mia domanda è: esiste un modo veramente efficace per risolvere il mio problema o devo pensare a memorizzare i valori in modo diverso? miei limiti sono i seguenti: - stdio.h/iostream solo - solo numeri interi - n < = 20.000.000 - n> = 2

#include <stdio.h> 

long long cat(long long l, long long m, long long n); 

int main(){ 
    long long n = 0; 
    long long val; 
    scanf("%lld", &n); 

    val = cat(1, 1, n/2); 

    printf("%lld", (val)); 

    return 0; 
} 

long long cat(long long q, long long p, long long n){ 
    if (n == 0) { 
     return (q/p) % 1000000007; 
    } 
    else { 
     q *= 4 * n - 2; 
    } 

    p *= (n + 1); 

    return cat(q, p, n - 1); 
} 

Answer 1

Per risolvere in modo efficiente, si desidera utilizzare modular arithmetic, con modular inverses sostituendo per divisione.

È semplice provare che, in assenza di overflow, (a * b) % c == ((a % c) * b) % c. Se stessimo semplicemente moltiplicando, potremmo ottenere risultati mod 1000000007 ad ogni passo e rimanere sempre entro i limiti di un numero intero a 64 bit. Il problema è la divisione. (a/b) % c non corrisponde necessariamente a ((a % c)/b) % c.

Per risolvere il problema con la divisione, utilizziamo gli invers modulari. Per i numeri interi a e c con c prime e a % c != 0, possiamo sempre trovare un numero intero b tale che a * b % c == 1. Questo significa che possiamo usare la moltiplicazione come divisione. Per qualsiasi numero intero d divisibile per a, (d * b) % c == (d/a) % c. Ciò significa che ((d % c) * b) % c == (d/a) % c, in modo che possiamo ridurre i risultati intermedi mod c senza rovinare la nostra capacità di dividere.

Il numero che vogliamo calcolare è del modulo (x1 * x2 * x3 * ...)/(y1 * y2 * y3 * ...) % 1000000007. Possiamo invece calcolare x = x1 % 1000000007 * x2 % 1000000007 * x3 % 1000000007 ... e y = y1 % 1000000007 * y2 % 1000000007 * y3 % 1000000007 ..., quindi calcolare l'inversa modulare z di utilizzando extended Euclidean algorithm e restituire (x * z) % 1000000007.

Answer 2

Se stai usando gcc o clang e Obiettivo a 64 bit, esiste un __int128 type. Questo ti dà bit in più su cui lavorare, ma ovviamente solo fino a un certo punto.

Molto probabilmente il modo più semplice per affrontare questo tipo di problema è usare una libreria "bignum", cioè una libreria che si occupa di rappresentare e fare aritmetica su numeri arbitrariamente grandi. L'esempio open source che è probabilmente il più popolare è libgmp - dovresti essere in grado di far funzionare abbastanza facilmente il tuo algoritmo. È anche ottimizzato per gli standard di prestazioni elevate.

Ovviamente è possibile reimplementarlo autonomamente, rappresentando i propri numeri come ad es. matrici di numeri interi di una certa dimensione. Dovrai implementare algoritmi per fare aritmetica di base come +, -, *, /,% te stesso. Se vuoi fare questo come esperienza di apprendimento va bene, ma non c'è vergogna nell'usare libgmp se vuoi concentrarti solo sull'algoritmo che stai cercando di implementare.