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.