Trova il numero di cifre non divisibile per X nella centesima riga del triangolo di Pascal - c #, algoritmo, logica, triangolo di pascal

Devo scoprire il numero di cifre che non sono divisibili per un numero x nella centesima riga del triangolo di Pascal.

L'algoritmo che ho applicato per trovare questo è: poiché il triangolo di Pascal ha potenze di 11 dalla seconda riga in poi, l'ennesima riga può essere trovata per 11 ^ (n-1) e può essere facilmente verificata per le quali le cifre non sono divisibili per x.

Come faccio a scoprirlo per numeri grandi quando n è uguale a 99 o 100? C'è qualche altro algoritmo che può essere applicato per trovare questo?

risposte:

Puoi calcolare direttamente i valori di pascal "striangolo usando fattoriali (n! / (n-k + 1)! (k-1)! ennesima riga, kth valore). Puoi iniziare con k = 1, calcolare in modo incrementale il coefficiente binomiale e in n / 2 passaggi puoi trovare il numero non divisibile per x.

scegli (n, k + 1) = scegli (n, k) * (n-k + 1) / k dove scegli (n, k) = (n! / (n-k + 1)! (k-1) !

Non hai bisogno di valori esatti della centesima riga del triangolo. Calcolare è OK value mod x. Costruisci il triangolo come al solito, ma applica l'operazione del modulo ovunque - non avrai bisogno di grandi numeri.