Read in my Cnblogs

提供复杂度的证明。感谢

性质一 当 $n\ge 9$，答案不大于 $1$。

证明：

引理一 $\forall i\in\mathbb N^{+},i\perp (i+1)$

证明：若 $d\mid i,d\mid (i+1)$，则 $d\mid 1$。

引理二 令 $d_i=\gcd(a_1,a_2,\dots,a_i+1,\dots,a_n)$，$\forall i,j\in[1,n]\cap\mathbb Z,d_i\perp d_j$

证明：考虑 $x,y\in[1,n]\cap\mathbb Z$，若 $d_x=1$ 或者 $d_y=1$ 则显然成立，考虑当 $d_x>1,d_y>1$ 的情况。根据定义存在 $d_x\mid y,d_y\mid x,d_x\mid(x+1),d_y\mid(y+1)$，若存在 $d>1,d\mid d_x,d\mid d_y$，那么 $d\mid x,d\mid y$，且 $d\mid(x+1),d\mid(y+1)$，则导出 $\gcd(x,x+1)\ge d>1,\gcd(y,y+1)\ge d>1$，即 $x\not\perp (x+1),y\not\perp(y+1)$，与引理一矛盾。

回到性质一，如果答案大于 $1$，则肯定满足 $\forall i,d_i>1$。根据定义对于一个数 $a_x$，$\forall j\neq x,d_j\mid a_x$，又 $d_i\perp d_j$，则 $\prod_{j\neq x}d_j\mid a_x$，因为 $a_x\le 10^7$ 所以即使 $d_j,j\neq x$ 是最小的几个质数，也只能放 $8$ 个，故 $n$ 必须不大于 $9$。

性质二 答案不大于 $11$。

证明：考虑一种构造，使得如果只操作第一个和第二个数，用不超过 $11$ 次就肯定能将两个数变成互质的。假设第一个数是 $a$，第二个数是 $b$。我们考虑让 $a$ 加 $r\in\{0,1,2,3,4,5\}$，那么首先考虑排除使得 $2\mid (a+r)$ 的 $r$，此时至少还剩 $3$ 个 $r$ 使得 $2\nmid (a+r)$。然后考虑排除 $3\mid (a+r)$，此时剩下的 $r$ 的差要么是 $2$ 要么是 $4$，故还有至多一个 $r$ 使得 $3\mid (a+r)$。那么还剩下两个。这两个 $r$ 的差不可能是 $5$，因为 $r=0,r=5$ 至少被排除了一个，因此这两个数的差必然小于 $5$，则其中最多也只有一个 $r$ 满足 $5\mid (a+r)$，所以还能剩下一个唯一的 $r$ 满足 $2\nmid (a+r),3\nmid (a+r),5\nmid (a+r)$。

我们找到这个 $r$ 之后，我们知道 $a+r\le 10^7+5$，在这个范围内，它又不被 $2,3,5$ 整除，则最多还有 $6$ 种质因子，而我们可以给 $b$ 加上 $c\in\{0,1,2,3,4,5,6\}$，一共 $7$ 种数，最坏情况下，可能存在 $6$ 个不同的 $c$ 满足 $b+c$ 刚好被这 $6$ 种质因子中的一个整除，但是我们还剩下一个可用的 $c$，一定不会被任何 $a+r$ 中的质因子整除，因此我们构造了一种方案，说明只需要 $11$ 个数就可以让序列中的任意两个数变得互质，整个序列也就互质了。

有了上述性质，我们就可以证明搜索的复杂度了，即 $\sum_{i=2}^{11}{n+r-1\choose r-1}$，当 $n=9$ 时，搜索量约为 $184755$。显然可通过。当 $n>9$ 时判断一下 $\gcd$ 是否已经为 $1$ 就好了。