[DTOI 2023] C. 不见故人

给定 $n, k$ 和序列 $\{a_n\}$，你同时有一个临时变量 $x$，你可以进行以下操作若干次（也可以是 $0$ 次），一次操作的流程是： 1. 选定一个区间 $[l,r]$，$\forall i\in[l,r]$，$x\leftarrow \gcd(a_l,a_{l+1},\cdots,a_r)$。 2. $\forall i\in[l,r]$，$a_i\leftarrow x$。 简而言之，你每次可以选定一个区间并将其中每个数变成这个区间的 $\gcd$。 一次操作的代价是 $r-l+1+k$，现在你希望把这个序列的每个数都变成相等的，求最小代价和。 ---- 如果您不了解 $\gcd$ 或者多元 $\gcd$ 的含义，可以参照如下定义： - $\gcd(a_1,a_2,\dots, a_k)$ 表示 $a_1,a_2,\dots, a_k$ 的最大公约数，即最大的能同时整除 $a_1,a_2,\dots, a_k$ 的正整数。 ## Input 第一行两个非负整数 $n,k$。 第二行 $n$ 个数，表示 $\{a_n\}$。 ## Output 一行一个数，表示答案。 [samples] ## Background 虽然 luanmenglei 已经是成熟的高中生了，但每次提起 luanmenglei 八年级的女朋友时，luanmenglei 都会沉浸在美好的回忆中，不可自拔。 ## Note #### 【样例 1 解释】 操作一次，选择区间 $[1,10]$。 #### 【样例 4】 见附加文件中的 `old/old4.in` 与 `old/old4.out`。 该样例满足测试点 $9\sim 12$ 的限制。 #### 【样例 5】 见附加文件中的 `old/old5.in` 与 `old/old5.out`。 该样例满足测试点 $13\sim 16$ 的限制。 #### 【数据范围与提示】 对于所有数据，保证 $1\leq n\leq 4\times 10^6$，$0\leq k\leq 10^9$，$1\leq a_i\leq 10^9$。 每个测试点的具体限制见下表： | 测试点编号 | $n\leq$ | $k,a_i\leq$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10^6$ | $10^9$ | 所有数都相等 | | $2\sim 4$ | $4$ | $10^9$ | 无 | | $5\sim 8$ | $100$ | $10^9$ | 无 | | $9\sim 12$ | $1000$ | $10^9$ | 无 | | $13\sim 16$ | $10^6$ | $10^9$ | 无 | | $17\sim 20$ | $4\times 10^6$ | $10^9$ | 无 | 本题的读入量较大，请选择较快的读入方式，下面提供一种读入策略： 请在代码的开头加入此行：`std::ios::sync_with_stdio(false);std::cin.tie(0);`。 请注意，加入本行后 `cin/cout` 的效率将大幅提高，保证其能在 `250 ms` 内读入所有数据，**但使用后你仅能使用 `cin/cout` 流读入数据。**