Пуговицы(#1018) A to B(#1020)
#1019

Задача g6_1019: Банки
Имеется N банок с целочисленными объемами V1, ..., Vn литров, пустой сосуд и кран с водой. Можно ли с помощью этих банок налить в сосуд ровно V литров воды?
Исходная информация содержится в файле input.txt в первой строчке - количество банок N<100, затем N строчек с объемами банок и в последней строчке объем сосуда.
Программа должна вывести в файл output.txt одно из двух слов YES! или NO.
Решение g6_1019:
5.03.02 - автором было найдено слабое место в задаче - решение исправлено ;)
С помощью двух банок мы можем без особых ухищрений саккумулировать в сосуде количество литров, равное их наибольшему общему делителю. Например, с помощью сосудов в 5 и 3 литра, мы можем набрать любое количество воды(проверено на опыте), а их НОД равен 1.
A*x - B*y = НОД(A, B), где A и B - объемы сосудов, а x и y - некоторые величины.
Теперь задача свелась к поиску НОД двух чисел. Постараемся сделать это побыстрее. Для этого воспользуемся алгоритмом Евклида. Из двух чисел выберем большее и заменим его на остаток от деления этого числа на меньшее. Будем повторять этот шаг до тех пор, пока одно из чисел не станет равно 0, при этом оставшееся число будет равно НОД этих чисел.
Найдя НОД объемов двух первых банок (НОД(V1, V2)) будем последовательно находить НОД(НОД(V1, V2), V3) и т.д. до Vn. Теперь, если объем делится нацело на НОД, то выводим "YES!", иначе "NO".
Если вам хотелось бы ускорить процесс поиска НОД (хотя он и так работает достаточно быстро) можете почитать первую главу книги А. Шеня Программирование: теоремы и задачи
Все.