A. Bestie
You are given an array $a$ consisting of $n$ integers $a_1,a_2, \dots ,a_n$. Friends asked you to make the greatest common divisor (GCD) of all numbers in the array equal to $1$. In one operation, you can do the following:
- Select an arbitrary index in the array $1 \leq i \leq n$;
- Make $a_i=\gcd{(a_i,i)}$, where $\gcd{(x,y)}$ denotes the GCD of integers $x$ and $y$. The cost of such an operation is $n−i+1$.
You need to find the minimum total cost of operations we need to perform so that the GCD of the all array numbers becomes equal to $1$.
Input
Each test consists of multiple test cases. The first line contains an integer $t$ $(1 \leq t \leq 5000)$ — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $n$ $(1 \leq n \leq 20)$ — the length of the array.
The second line of each test case contains $n$ integers $a_1,a_2, \dots ,a_n$ $(1 \leq a_i \leq {10}^{9})$ — the elements of the array.
Output
For each test case, output a single integer — the minimum total cost of operations that will need to be performed so that the GCD of all numbers in the array becomes equal to $1$.
We can show that it’s always possible to do so.
Example
input
9 1 1 1 2 2 2 4 3 3 6 9 4 5 10 15 20 5 120 60 80 40 80 6 150 90 180 120 60 30 6 2 4 6 9 12 18 6 30 60 90 120 125 125
output
0 1 2 2 1 3 3 0 1
Note
In the first test case, the GCD of the entire array is already equal to $1$, so there is no need to perform operations.
In the second test case, select $i=1$. After this operation, $a_1=\gcd{(2,1)}=1$. The cost of this operation is $1$.
In the third test case, you can select $i=1$, after that the array a will be equal to $[1,4]$. The GCD of this array is $1$, and the total cost is $2$.
In the fourth test case, you can select $i=2$, after that the array a will be equal to $[3,2,9]$. The GCD of this array is $1$, and the total cost is $2$.
In the sixth test case, you can select $i=4$ and $i=5$, after that the array a will be equal to $[120,60,80,4,5]$. The GCD of this array is $1$, and the total cost is $3$.
解题思路
A题，比赛的时候卡了一个小时，哈哈。
先说一个重要的结论：对于一个整数$n$，有$\gcd{(n – 1, n)} = 1$。证明如下：
先证$\gcd{(a, b)} = \gcd{(a – b, b)}$。设$\gcd{(a, b)} = d$，那么有$a = d \times x$，$b = d \times y$，并且$x$和$y$互质（如果$x$和$y$不互质那么$a$和$b$的最大公约数就不是$d$了）。证明$d$是$a – b$的公约数：有$a – b = d \times x – d \times y = d \times (x – y)$，即$d \mid a – b$。又因为$d \mid b$，因此$d$是$a – b$和$b$的公约数。下面证$d$是$a – b$和$b$的最大公约数：反证法，如果存在一个$e > d$，且满足$e \mid a – b$，$e \mid b$，那么可以得到$e \mid a$，即$a$和$b$存在一个比$d$更大的公约数，这就与$\gcd{(a, b)} = d$矛盾了，因此$d$是$a – b$和$b$的最大公约数，即$\gcd{(a – b, b)} = \gcd{(a, b)} = d$。同理可证$\gcd{(a, b)} = \gcd{(a – b, a)}$。
因此有结论$\gcd{(a, b)} = \gcd{(a – b, b)} = \gcd{(a – b, a)}$。
因为$\gcd{(n, 1)} = 1$，因此有$\gcd{(n, 1)} = \gcd{(n – 1, n)} = 1$，得证。
对于这道题目，假设$d = \gcd{(a_1, a_2, \dots a_n)}$，要使得$d$最终变为$1$，我们可以选择任意一个下标$i$以及$i-1$来与$d$求最大公约数，最后得到的结果必然是$1$（因为$\gcd{(i – 1, i)} = 1$，因此$\gcd{(d, i – 1, i)} = \gcd{(d, \gcd{(i – 1, i)})} = 1$）。为了使得代价最小，这里$i$取$n$，那么这样就可以保证答案$\leq 3$。
下面分类讨论：
- 如果$d = 1$，那么就不用操作，答案为$0$。
- 否则尝试只选择下标$n$，如果有$\gcd{(d, n)} = 1$，那么答案为$1$。
- 否则尝试只选择下标$n-1$，如果有$\gcd{(d, n-1)} = 1$，那么答案为$2$。
- 否则选择下标$n$和下标$n-1$，那么答案为$3$。
AC代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int gcd(int a, int b) { 5 return b ? gcd(b, a % b) : a; 6 } 7 8 void solve() { 9 int n; 10 scanf("%d", &n); 11 12 int d = 0; 13 for (int i = 0; i < n; i++) { 14 int x; 15 scanf("%d", &x); 16 d = gcd(d, x); 17 } 18 19 int ret = 3; 20 if (d == 1) ret = 0; 21 else if (gcd(d, n) == 1) ret = 1; 22 else if (gcd(d, n - 1) == 1) ret = 2; 23 24 printf("%d\n", ret); 25 } 26 27 int main() { 28 int t; 29 scanf("%d", &t); 30 while (t--) { 31 solve(); 32 } 33 34 return 0; 35 }
参考资料
Codeforces Round #830 (Div. 2) Editorial：https://codeforces.com/blog/entry/108327
$a>b>0$，$a,b$均为正整数, $\gcd(a, b)=\gcd(a-b,a)$吗？- 张学涵的回答 – 知乎：https://www.zhihu.com/question/441593398/answer/1703905776
原文地址：http://www.cnblogs.com/onlyblues/p/16820019.html
