1779: 签到题
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：58
解决：16
题目描述
给定一个整数数组a，它包含n个整数。
你可以对这个数组进行如下操作：选择一个数i（1 <= i <= n)，令a[i] = gcd(a[i],i)，（gcd(x, y)是x和y的最大公约数）。
进行一次上述操作的成本是n - i + 1。
现在请你求出通过任意次上述操作使数组中所有数字的最大公约数等于1的最小成本。(当数组只有一个数时，所有数字的最大公约数按这个数字本身算)
你可以对这个数组进行如下操作：选择一个数i（1 <= i <= n)，令a[i] = gcd(a[i],i)，（gcd(x, y)是x和y的最大公约数）。
进行一次上述操作的成本是n - i + 1。
现在请你求出通过任意次上述操作使数组中所有数字的最大公约数等于1的最小成本。(当数组只有一个数时，所有数字的最大公约数按这个数字本身算)
输入
第一行，一个正整数n，数组元素数量。 1 <= n <= 20
第二行，n个正整数， 1 <= a[i] <= 1e9
第二行，n个正整数， 1 <= a[i] <= 1e9
输出
一行，一个正整数，所需要的最小成本
样例输入 复制
5
120 60 80 40 80样例输出 复制
3提示
样例解释：
在样例中，你可以对a[4]和a[5]进行操作，在两次操作后数组变为 [120,60,80,4,5]，此时数组中所有元素的最大公约为1，需要的成本为3。
在样例中，你可以对a[4]和a[5]进行操作，在两次操作后数组变为 [120,60,80,4,5]，此时数组中所有元素的最大公约为1，需要的成本为3。