Verifica di rappresentabilità con due monete coprime

I tagli devono essere coprimi, condizione che consente una soluzione esatta tramite aritmetica modulare. Quando l'obiettivo è rappresentabile, il risultato include una coppia precisa di quantità di monete; altrimenti segnala chiaramente che tale coppia non esiste. Lo strumento è utile per esperimenti numerici, esercizi di matematica discreta, progettazione dei tagli e controllo di combinazioni di dimensione esatta senza una ricerca esaustiva.

Definisca con precisione il problema delle due monete

Inserisca due tagli interi positivi come coin_a e coin_b, quindi un obiettivo intero non negativo. Il verificatore cerca interi non negativi count_a e count_b tali che la quantità del primo tipo moltiplicata per coin_a, sommata alla quantità del secondo tipo moltiplicata per coin_b, coincida esattamente con l'obiettivo. Un risultato rappresentabile non indica quindi un valore vicino o una combinazione inferiore a un budget: l'uguaglianza deve essere esatta e nessuna quantità può essere negativa. Zero è un obiettivo valido, perché si ottiene scegliendo zero monete di entrambi i tipi. Anche un taglio pari a uno è valido e rende rappresentabile ogni obiettivo non negativo. Tutti e tre gli input devono essere interi sicuri; valori decimali, stringhe numeriche, infiniti e interi oltre l'intervallo esatto di JavaScript vengono rifiutati anziché essere arrotondati silenziosamente. I due tagli devono inoltre essere coprimi, cioè avere massimo comune divisore uguale a uno.

Comprenda il calcolo modulare

Poiché i tagli sono coprimi, la prima moneta possiede un inverso moltiplicativo modulo la seconda. Il verificatore calcola tale inverso con l'algoritmo euclideo esteso e lo usa per individuare l'unico candidato count_a compreso tra zero e coin_b meno uno che soddisfa la congruenza richiesta. Sottraendo dall'obiettivo il valore apportato da queste prime monete rimane una differenza. Se è non negativa, è divisibile per coin_b e produce un count_b valido; la risposta include entrambe le quantità come prova concreta. Se la differenza è negativa, non esiste alcuna rappresentazione non negativa. La conclusione è completa, non euristica: ogni altra soluzione intera modifica count_a di un multiplo intero di coin_b e count_b, in direzione opposta, di un multiplo intero di coin_a. Partendo dal più piccolo candidato non negativo per count_a, una differenza negativa non può essere corretta senza rendere count_a negativo. Il metodo opera in tempo logaritmico invece di provare una per una numerose quantità possibili.

Interpreti i risultati e gli errori di input

Una risposta con representable impostato su vero include count_a e count_b. Moltiplicando ciascuna quantità per il taglio corrispondente si ricostruisce l'obiettivo. La coppia restituita è una soluzione valida; un obiettivo abbastanza grande può avere più rappresentazioni e il verificatore non intende elencarle tutte né ottimizzarle. Una risposta falsa omette le quantità perché nessuna coppia è applicabile. Occorre distinguere un errore dovuto a monete non coprime da un risultato falso. Falso significa che l'input rispetta il contratto, ma quello specifico obiettivo non può essere formato. Un errore indica invece che la coppia di tagli è fuori dal dominio definito dalla capacità, quindi non viene emessa alcuna decisione di rappresentabilità. Per esempio, le monete 6 e 9 condividono il fattore 3 e vengono rifiutate anche quando l'obiettivo è divisibile per 3. Questa distinzione impedisce di confondere una violazione del dominio con un'impossibilità matematica. Il calcolo è deterministico, non usa servizi di rete e restituisce lo stesso risultato per gli stessi input interi esatti sia nel browser sia tramite API.