#D. v我0.5元,我带你飞

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个长度为 $n$ 的数组。你可以操作任意次，每次操作都在数组中选择两个数a，b，让a，b都除以他们的最大公约数。问最少操作几次可以使整个数组的最大公约数为1.

第一行输入 $n$ ( $2$ $≤$ $n$ $≤$ $100000$ )第二行 $n$ 个整数 $ai$ （ $1$ $≤$ $ai$ $≤$ $100000$ ）。

输出一个整数 $x$ 代表最终答案。

2
2 2