e-olymp 4482. В стране невыученных уроков 2

Задача

Теперь у Вити есть программа, которая помогает ему быстро находить НОД многих чисел. Поэтому стражи решили изменить правила: теперь Витя должен найти наибольший общий делитель (НОД) чисел на промежутке [l; r], а стражи – наименьшее общее кратное (НОК), у кого получится число меньше, тот и выиграет.

Входные данные

Первая строка содержит количество элементов в массивеn (1n106). Во второй строке находится n чисел – элементы ai (1ai109) массива. В третьей строке находится количество запросовm (1m 105). Далее в m строках находится по три числа q, l, r (1lrn). Если q = 1, требуется определить победителя для промежутка [l; r], если q = 2, то нужно заменить элемент в позиции l на число r.

Выходные данные

Для каждого запроса с номером 1 в отдельной строке выведите строку «wins«, если Витя выиграл, строку «loser«, если он проиграл и «draw«, если была ничья.

Решение

В данной задаче нам нужно реализовать дерево отрезков, но поменять функцию которую определяет значение в узлах. Прочитав условие можно понять, что ответ «loser» мы не выведем никогда, так как НОД не может быть больше НОК. Тогда остается определить когда выводить «wins» или «draw». НОД и НОК некоторого количества чисел равны тогда и только тогда, когда все числы для которых мы считаем НОД и НОК равны между собой. Поэтому ассоциативной функцией для построения дерева выберем функцию равенства, если числа равны возвращаем само число, иначе 0. Тогда для ответа на вопрос задачи просто следует узнать что находится в соответсвующем узле.
Если это 0, то НОК больше НОД, иначе они равны и мы выведем «draw».

Код

Тесты

Входные данные Выходные данные
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 1
wins
wins
wins
draw
5
7 7 7 7 7
4
1 1 5
2 2 1
1 1 5
1 3 5
draw
wins
draw

Задача взята отсюда.

Решенная задача на e-olymp.

Код программы.

 

Алина Гончарова
Алина Гончарова

Latest posts by Алина Гончарова (see all)

Добавить комментарий