Come calcolare il coefficiente binomiale C (n, r) modulo qualche potenza primaria?

-1

Come calcolare C (n, r) modulo m, m è di forma p ^ a, dove p è primo.

Qui C (n, r) significa n scegli r. L'intervallo di n ed r è ampio (dell'ordine di 10 ^ 18), quindi non può essere risolto calcolando la potenza dei numeri primi. Anche m è inferiore a 10 ^ 6. Ho provato a leggere la generalizzazione del Teorema di Lucas, ma non riuscivo a capirlo. Sarà davvero utile se qualcuno potrebbe spiegare un metodo fattibile per risolvere il problema.

Fino ad ora ho provato questo. Ho memorizzato ogni numero primo da 1 a n in un array p []. Quindi calcolato la potenza di pi 1 < = i < = | p | Locanda! e l'ho aggiunto a arr [i]. Allo stesso modo calcolato il potere di pi 1 < = i < = | p | da 1 a r in r! e sottratto da arr [i]. Lo stesso per (n-r) !. Quindi moltiplicato (p [i] ^ arr [i])% (p ^ a) per rispondere durante l'assunzione di modulo. Ma questo funziona in O (n), che è troppo lento per i vincoli sopra menzionati.

C'è una citazione nella pagina wikipedia di il teorema di Lucas per la forma generalizzata del teorema di Lucas ma il collegamento non funziona.

    
posta abc xyz 16.05.2017 - 22:40
fonte

1 risposta

0

Se stai cercando di risolvere un problema in un concorso di programmazione, non leggere oltre, perché l'uso di un aiuto esterno è imbrogli .

Molto semplice. Stai calcolando un prodotto di numeri x (i) modulo m. Questi numeri x (i) sono numeri interi consecutivi. Se ce ne sono n o più, allora uno deve essere uguale a 0 (modulo m). E in tal caso, l'intero prodotto è 0 (modulo m). In realtà, se ci sono un * p o più, allora hai un numero divisibile per p, quindi il prodotto è divisibile per m = p ^ a, quindi il prodotto è 0.

Pertanto, tutti i casi in cui il prodotto non è 0 modulo m possono essere risolti con meno di m moltiplicazioni.

    
risposta data 17.05.2017 - 07:54
fonte

Leggi altre domande sui tag