Задача на gcd, не понятна логика условия
В начале игры у вас есть массив a длины n. За один ход можно выбрать два соседних элемента и заменить один из них на наибольший общий делитель этих двух чисел. То есть из двух соседних чисел x и y можно получить либо gcd(x,y) и y, либо x и gcd(x,y). за какое минимальное число ходов можно превратить весь массив в единицы.
Есть примеры:
Элемент списка
- 2 2 3 4 6 (результат работы 5)
- 2 6 9 (результат работы 4)
- 2 4 6 8 (-1, т.е. этого добиться невозможно)
Не понимаю почему такие результаты, ведь есть посмотреть например на 2 пример, то можем получить 1 6 3 или 2 1 3, и далее ничего...
Ответы (1 шт):
Давайте рассмотрим ваш второй пример
2 6 9
gcd 2 3
2 2 9
gcd 2 1
2 2 1
gcd 2 1
1 2 1
gcd 1 1
1 1 1
Все верно, 4 шага...
Как вы получаете 1 6 3 — непонятно, но и эту тройку легко превратить в 1 1 3, а затем 1 1 1...
Вот 2 4 6 8 сведется в лучшем случае к 2 2 2 2, а дальше — никак..
P.S. Кстати, интересная задачка. Если в списке есть 1 — то количество ходов просто равно количеству неединичных элементов. Если есть пара взаимнопростых чисел, стоящих рядом — то просто равно количеству элементов. Если gcd всех элементов не 1 — то ничего не получится. А вот найти кратчайший способ получить хоть одну 1, если все пары соседних элементов не взаимно просты? Как я понимаю, надо искать минимальный набор элементов, у которых gcd == 1, но как это сделать максимально быстро?