Задача №114743. Лапша быстрого приготовления
Ву проголодался после интенсивной тренировки и отправился в ближайший магазин, чтобы приобрести его любимую лапшу быстрого приготовления. После того, как Ву расплатился, кассир задал ему интересную задачу.
Дан двудольный граф, в вершинах правой доли которого записаны положительные целые числа. Для подмножества вершин \(S\) левой доли определим \(N(S)\) как множество вершин правой доли, смежной хотя бы с одной из вершин \(S\), а \(f(S)\) — как сумму чисел, записанных в вершинах \(N(S)\). Требуется найти наибольший общий делитель чисел \(f(S)\) для всех возможных непустых подмножеств \(S\).
Ву слишком устал во время тренировки, чтобы справиться с такой задачей. Помогите ему!
В первой строке записано целое число \(t\) (\(1 \leq t \leq 500\,000\)) — количество тестовых случаев, для которых требуется решить задачу. Затем следует описание тестовых случаев.
В первой строке каждого описания записаны два целых числа \(n\) и \(m\) (\(1~\leq~n,~m~\leq~500\,000\)) — количество вершин в каждой из долей графа и количество рёбер, соответственно.
Во второй строке записано \(n\) целых чисел \(c_i\) (\(1 \leq c_i \leq 10^{12}\)), \(i\)-е из которых задаёт число, записанное в \(i\)-й вершине правой доли графа.
В следующих \(m\) строках записаны пары целых чисел \(u_i\) и \(v_i\) (\(1 \leq u_i, v_i \leq n\)), обозначающие ребро между \(u_i\)-й вершиной левой доли графа и \(v_i\)-й вершиной правой доли графа. Гарантируется, что в графе нет кратных рёбер.
Тестовые случаи разделены пустой строкой. Сумма значений \(n\) по всем тестовым случаям не превосходит \(500\,000\), сумма значений \(m\) по всем тестовым случаям также не превосходит \(500\,000\).
Для каждого тестового случая выведите единственное число — искомый наибольший общий делитель.
Наибольшим общим делителем множества чисел называется наибольшее целое число \(g\) такое, что все элементы множества без остатка делятся на \(g\).
В первом примере все вершины левой доли соединены ребром со всеми вершинами правой доли, поэтому значение \(f(S)\) для любого непустого подмножества будет равно \(2\), соответственно наибольший общий делитель этих значений будет также равен \(2\).
Во втором примере подмножество \(\{1\}\) вершин левой доли соединено ребром с вершинами \(\{1, 2\}\) правой доли, сумма значений в которых равна \(2\), а подмножество \(\{1, 2\}\) вершин левой доли соединено рёбрами с вершинами \(\{1, 2, 3\}\) правой доли, сумма значений в которых равна \(3\). Таким образом, \(f(\{1\}) = 2\), \(f(\{1, 2\}) = 3\), что значит, что наибольший общий делитель всех чисел \(f(S)\) равен \(1\).
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Пусть \(\sum n\) обозначает сумму \(n\) по всем тестовым случаям, а \(\sum m\) сумму \(m\).
| Дополнительные ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(\sum{n}\) | \(\sum{m}\) | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 21 | \(n \leq 20\) | \(m \leq 400\) | \(\sum{n} \leq 100\) | \(\sum{m} \leq 2000\) | |
| 2 | 33 | \(n \leq 5000\) | \(m \leq 5000\) | \(\sum{n} \leq 10\,000\) | \(\sum{m} \leq 10\,000\) | |
| 3 | 46 | – | – | – | – | Offline-проверка. |
3 2 4 1 1 1 1 1 2 2 1 2 2 3 4 1 1 1 1 1 1 2 2 2 2 3 4 7 36 31 96 29 1 2 1 3 1 4 2 2 2 4 3 1 4 3
2 1 12