L'Atelier Monstre

Cet article aborde le calcul d'une expression mathématique complexe impliquant des sommes modulaires, en utilisant des techniques avancées telles que le théorème de Lucas et le théorème des restes chinois. Le problème consiste à évaluer la somme suivante, où p est un nombre premier. Le nombre premier donné est p = 999911659. Les facteurs premie ...

Énoncé du problème Soit une fonction f définie pour tout entier positif n vérifiant : ∑d|n f(d) = n Étant donnés n entiers a1, a2, …, an, calculer ∑i=1n f(ai). Méthode de résolution La fonction f n'est autre que l'indicatrice d'Euler φ. Elle possède les propriétés suivantes : Si q = nm avec n et m premiers entre eux, alors f(q) = f(n) × f(m). ...

En travaillant avec des polynômes, on constate rapidement que les complexités algorithmiques peuvent croître de manière exponentielle lors d'appels de fonctions imbriqués, transformant une légère différence initiale en un écart considérable. Définition des bornes Dans de nombreux problèmes, seuls les premiers termes d'un polynôme nous intéresse ...

L'algorithme de recherche binaire standard peut retourner n'importe lequel des éléments correspondants lorsque plusieurs occurrences existent. Pour garantir le retour de la première occurence, une modification est nécessaire. En utilisant le tableau défini par int donnees[8] = { 1, 2, 2, 2, 5, 6, 8, 9 };, l'implémentation suivante ajuste la log ...