L'Atelier Monstre

Introduction au plus court chemin par congruence Le plus court chemin par congruence est une technique algorithmique basée sur la théorie des nombres, utilisée pour modéliser des états via des classes de congruence. Elle transforme des problèmes de combinaison linéaire en graphes où les nœuds représentent des restes modulo un entier donné, et l ...

É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). ...

Crible linéaire L'objectif est de déterminer tous les nombres premiers jusqu'à une borne \(n\), avec \(n \le 10^8\). Le crible d'Ératosthène classique a une complexité de \(O(n \ln \ln n)\), car il marque les multiples de chaque nombre premier à plusieurs reprises. Pour une efficacité optimale, on utilise un crible linéaire où chaque nombre com ...

P8255 Jeu Mathématique Si x ne divise pas z, aucune solution n'exitse. En décomposant x = d*a et y = d*b avec gcd(a,b) = 1, on a gcd(x,y) = d. Ainsi, z = x * y * gcd(x,y) = d^3 * a * b. À partir de x et z, on calcule le quotient q = z/x = d^2 * b. Ensuite, on évalue g = gcd(q, x^2) = d^2. Si g n'est pas un carré parfait, il n'y a pas de solutio ...