Vérifier une somme avec deux pièces copremières

Les valeurs doivent être copremières, ce qui permet une résolution exacte par arithmétique modulaire. Si la cible est représentable, le résultat fournit une paire précise de nombres de pièces ; sinon, il indique clairement qu'aucune paire ne convient. Cet outil sert aux expériences numériques, aux exercices de mathématiques discrètes, à la conception de valeurs faciales et à la validation de combinaisons exactes sans recherche exhaustive.

Définissez précisément le problème des deux pièces

Saisissez deux valeurs de pièces entières et positives dans coin_a et coin_b, puis une cible entière non négative. Le vérificateur cherche des entiers non négatifs count_a et count_b tels que le nombre de premières pièces multiplié par coin_a, additionné au nombre de secondes pièces multiplié par coin_b, soit strictement égal à la cible. Un résultat représentable ne correspond donc ni à une valeur approchée ni à une combinaison simplement inférieure à un budget : l'égalité doit être exacte et aucun nombre ne peut être négatif. Zéro constitue une cible valide, car aucune pièce de chaque type suffit à le produire. Une valeur faciale égale à un est également admise et rend toute cible non négative représentable. Les trois entrées doivent être des entiers sûrs ; les décimales, chaînes numériques, infinis et entiers dépassant la plage exacte de JavaScript sont refusés afin d'éviter tout arrondi silencieux. Enfin, les deux valeurs doivent être copremières : leur plus grand commun diviseur doit valoir un.

Comprenez le calcul modulaire

Puisque les valeurs faciales sont copremières, la première possède un inverse multiplicatif modulo la seconde. Le vérificateur calcule cet inverse avec l'algorithme d'Euclide étendu, puis s'en sert pour trouver l'unique candidat count_a compris entre zéro et coin_b moins un qui respecte la congruence requise. Une fois la contribution de ces premières pièces soustraite de la cible, il reste une différence. Si elle est non négative, elle est divisible par coin_b et donne un count_b valide ; la réponse fournit alors les deux nombres comme preuve concrète. Si la différence est négative, aucune représentation non négative n'existe. Cette conclusion est complète et non heuristique : toute autre solution entière modifie count_a d'un multiple entier de coin_b et count_b, dans le sens opposé, d'un multiple entier de coin_a. Comme le calcul part du plus petit candidat non négatif pour count_a, une différence négative ne peut être corrigée sans rendre count_a négatif. La méthode s'exécute en temps logarithmique sans essayer successivement de nombreux nombres de pièces.

Interprétez les résultats et les erreurs de saisie

Une réponse où representable vaut vrai contient count_a et count_b. La multiplication de chaque nombre par la valeur faciale correspondante reconstitue la cible. La paire renvoyée est une preuve valide ; une cible assez grande peut posséder plusieurs représentations, mais le vérificateur ne prétend ni toutes les énumérer ni les optimiser. Une réponse fausse omet les nombres, puisqu'aucune paire ne s'applique. Il faut distinguer une erreur de valeurs non copremières d'un résultat faux. Faux signifie que l'entrée respecte le contrat, mais que cette cible précise ne peut pas être formée. Une erreur signifie que la paire sort du domaine défini par cette capacité ; aucune décision de représentabilité n'est alors fournie. Par exemple, les pièces 6 et 9 ont le facteur commun 3 et sont refusées, même si la cible est divisible par 3. Cette distinction évite de confondre une violation du domaine et une impossibilité mathématique. Le calcul est déterministe, n'utilise aucun service réseau et produit le même résultat avec les mêmes entiers exacts dans le navigateur et via l'API.