L'Atelier Monstre

Soit \(p\) un nombre premier. Nous notons \(v_p(n)\) la valuation \(p\)-adique de \(n\), et \((n)_p\) le quotient de \(n\) par la plus grande puissance de \(p\) qui le divise. Ainsi, on a \(n = p^{v_p(n)} (n)_p\). Théorème de Lucas Le théorème de Lucas permet de calculer un grand coefficient binomial modulo un petit nombre premier. Il évite les ...

A. Génération de Chaînes Binaires (P6191) On commence par compter les solutions avec 0 ou 1 seul '1'. Ensuite, on modélise la séquence comme une succession de blocs "1 suivi de k zéros", terminée par un '1'. Pour i occurrences de '1', la longueur minimale est j = (k + 1)(i - 1) + 1. Si j dépasse n, on arrête. Sinon, on calcule le nomb ...