Задача №114642. Фокус с делением и умножением
Наверняка вы знаете много математических фокусов. В этой задаче вам предлагается продемонстрировать свои умения в одном из таких фокусов.
У вас есть массив из различных натуральных чисел \(a_1, a_2, \ldots, a_n\). Помимо этого, перед вами стоит стол, на котором лежат \(10^{18}\) карточек, на которых записаны все натуральные числа от \(1\) до \(10^{18}\), каждое ровно на одной карточке.
Вы можете подойти к столу и взять карточку с числом \(x\). После этого вы можете выбрать ровно одно любое число \(a_i\) в вашем массиве и поменять его либо на \(\frac{a_i}{x}\), либо на \(a_i \cdot x\). При этом делить \(a_i\) на \(x\) разрешается только в случае, если \(a_i\) делится на \(x\). Таким образом все числа в вашем массиве должны оставаться натуральными. После выполнения данной операции использованная карточка выкидывается и больше никогда не возвращается на стол.
Вы хотите несколько раз взять со стола карточки и выполнить операции таким образом, чтобы в итоге все числа массива оказались равными. Определите, какое минимальное количество карточек потребуется взять со стола, чтобы совершить этот фокус. Гарантируется, что хотя бы один способ сделать все числа в массиве равными существует.
В первой строке находится одно целое число \(n\) (\(1 \leq n \leq 200\,000\)) — количество чисел в вашем массиве.
Во второй строке находятся \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_1 < a_2 < \ldots < a_n \leq 10^{18}\)), разделенных пробелами. Для удобства элементы массива даны в возрастающем порядке.
Выведите минимальное количество карточек, которое нужно взять со стола, чтобы сделать все числа массива равными с помощью операций деления и умножения, описанных в условии задачи.
В первом тесте, можно подойти к столу и взять карточку, на которой написано число \(2\). После этого можно выбрать элемент массива \(a_2 = 2\) и заменить его на \(\frac{2}{2} = 1\). Таким образом, все числа массива станут равны \(1\).
Во втором тесте можно подойти к столу пять раз и брать карточки, на которых записаны числа \(32, 24, 12, 6, 4\) и умножать на них первый, второй, третий, четвертый и пятый элемент массива, соответсвенно. Тогда все числа массива станут равны \(72\).
В третьем тесте можно подойти к столу, взять карточку с числом \(3\) и умножить \(a_1\) на него. После этого можно взять карточку с числом \(2\) и поделить \(a_3\) на него. Таким образом получится, что все числа массива равны \(717\).
2 1 2
1
5 2 3 6 12 18
5
3 239 717 1434
2