Verificador de representação com duas moedas coprimas

As denominações precisam ser coprimas, condição que permite resolver o problema com precisão por aritmética modular. Quando o alvo é representável, o resultado traz um par exato de quantidades de moedas; caso contrário, informa claramente que esse par não existe. A ferramenta é útil em experimentos numéricos, exercícios de matemática discreta, projetos de denominações e validação de combinações com tamanho exato sem busca exaustiva.

Defina corretamente o problema das duas moedas

Informe duas denominações inteiras positivas em coin_a e coin_b e, em seguida, um alvo inteiro não negativo. O verificador procura inteiros não negativos count_a e count_b para os quais a quantidade da primeira moeda multiplicada por coin_a, somada à quantidade da segunda multiplicada por coin_b, seja exatamente igual ao alvo. Portanto, um resultado representável não indica apenas um valor próximo ou uma combinação abaixo de um orçamento: a igualdade precisa ser exata e nenhuma quantidade pode ser negativa. Zero é um alvo válido, pois pode ser produzido usando zero moedas de cada tipo. Uma denominação igual a um também é válida e torna representável todo alvo não negativo. As três entradas devem ser inteiros seguros; valores decimais, textos numéricos, infinitos e inteiros fora da faixa exata do JavaScript são recusados para impedir arredondamentos silenciosos. As denominações também precisam ser coprimas, isto é, seu máximo divisor comum deve ser um.

Entenda o cálculo modular

Como as denominações são coprimas, a primeira moeda tem um inverso multiplicativo módulo a segunda. O verificador calcula esse inverso com o algoritmo de Euclides estendido e o utiliza para encontrar o único candidato a count_a entre zero e coin_b menos um que satisfaz a congruência necessária. Ao subtrair do alvo o valor fornecido por essas primeiras moedas, resta uma diferença. Se ela for não negativa, será divisível por coin_b e produzirá um count_b válido; a resposta inclui as duas quantidades como uma prova concreta. Se a diferença for negativa, não existe representação não negativa. Essa conclusão é completa, e não uma heurística: toda outra solução inteira altera count_a por um múltiplo inteiro de coin_b e altera count_b no sentido oposto por um múltiplo inteiro de coin_a. Como o cálculo começa pelo menor candidato não negativo a count_a, uma diferença negativa não pode ser corrigida sem tornar count_a negativo. O método tem tempo logarítmico e evita testar uma longa sequência de quantidades possíveis.

Interprete resultados e erros de entrada

Uma resposta com representable verdadeiro inclui count_a e count_b. Multiplicar cada quantidade pela denominação correspondente recompõe o alvo. O par retornado é uma solução válida; um alvo suficientemente grande pode ter várias representações, e o verificador não pretende listar nem otimizar todas elas. Uma resposta falsa omite as quantidades porque nenhum par se aplica. Diferencie um erro de moedas não coprimas de um resultado falso. Falso significa que a entrada respeita o contrato, mas o alvo específico não pode ser formado. Um erro significa que o par de denominações está fora do domínio definido por esta capacidade e, portanto, nenhuma decisão de representabilidade é emitida. Por exemplo, as moedas 6 e 9 compartilham o fator 3 e são recusadas mesmo quando o alvo é divisível por 3. Essa distinção evita confundir uma violação de domínio com impossibilidade matemática. O cálculo é determinístico, não usa serviços de rede e apresenta o mesmo resultado para as mesmas entradas inteiras exatas no navegador e na API.