Проверка чисел куриных самородков с разными парами монет без использования петель
Извиняюсь за глупое название вопроса. Мне дали в Java неклассифицированную задачу по существу определить, существуют ли два положительных целых числа x и y, такие что ax+by=c, где указаны a, b и c.
Контекст для этого заключается в том, что вам даны две монеты со значениями a и b, и вы должны определить, могут ли они каким-либо образом объединяться, чтобы равняться сумме c. Подвох в том, что ваш код не должен включать циклы какого-либо вида или рекурсивные функции.
До сих пор я определил, что алгоритм Евклида кажется полезным для такого рода проблем; поскольку нахождение наибольшего общего делителя a и b может доказать существование x и y в виде целых чисел, которое завершает уравнение. Проблема в том, что x и y все еще могут быть отрицательными, как в случае с множеством [3,7,11]. С наибольшим общим делителем между 3 и 7, равным 1, их можно объединить, чтобы получить от 11 до 3(-1)+7(2).
Поскольку вы, очевидно, не можете использовать отрицательное количество монет, 11 не будет "числом куриных самородков" (в связи с проблемой "Цыпленок МакНуггет", которую я считаю уместной). Так что я ищу либо совершенно другой метод попытки сделать это без каких-либо циклов, либо совет о том, как на самом деле определить значения x и y, чтобы увидеть, являются ли они отрицательными.
Я не обязательно ищу код для этого, просто любой совет или руководство поможет. Если у вас нет решения, но вы хотите подумать об этом, рекомендуем прочитать расширенный евклидов алгоритм, идентичность Безу, диофантовы уравнения и теорему Цикла МакНуггета.