有一个长度为 n n n 的数组 a 1 , ⋯   , a n a_1,\cdots,a_n a1​,⋯,an​，每次选相邻的两个数 a i , a i + 1 a_i,a_{i+1} ai​,ai+1​，花费代价 a i + a i + 1 a_i+a_{i+1} ai​+ai+1​ 把它们合并成 gcd ⁡ ( a i , a i + 1 ) \gcd(a_i,a_{i+1}) gcd(ai​,ai+1​)。求把整个序列合并起来的最小代价。

   n ≤ 2 × 1 0 5 ,   1 ≤ a i ≤ 1 0 12 n \leq 2 \times 10^5,~1 \leq a_i \leq 10^{12} n≤2×105, 1≤ai​≤1012   2s

\\ \\ \\

  这题推性质好强啊。。

  首先可以 O ( n 3 ) O(n^3) O(n3) 区间 dp： O ( n 2 ) O(n^2) O(n2) 枚举状态 [ l , r ] [l,r] [l,r]， O ( n ) O(n) O(n) 转移。（可能带个 log ⁡ \log log）

  然后发现 O ( n ) O(n) O(n) 转移是不必要的，最优情况肯定是从一个点出发不停地往左右扩展，即已合并的区域总是一个区间（反证法，假设最后一步合并 [ l , m i d ] , [ m i d + 1 , r ] [l,mid],[mid+1,r] [l,mid],[mid+1,r]，那么两个区间必有一个 gcd ⁡ \gcd gcd 更小，先做出小的再蚕食大的肯定更优），于是就 O ( n 2 ) O(n^2) O(n2) 了。（可能带个 log ⁡ \log log）

  这时需要两条性质：（此处直接搬uoj题解）

  引理 1：给 k k k 个数求 gcd ⁡ \gcd gcd，直接递推调用欧几里得算法，时间复杂度为 Θ ( k + log ⁡ a ) Θ(k+\log a) Θ(k+loga)。   注意到欧几里得算法执行 ( a , b ) (a,b) (a,b) 的过程与 ( a gcd ⁡ ( a , b ) , b gcd ⁡ ( a , b ) ) (\frac a{\gcd(a,b)},\frac b{\gcd(a,b)}) (gcd(a,b)a​,gcd(a,b)b​) 相同，所以我们可以得到一个复杂度的表示 Θ ( log ⁡ a gcd ⁡ ( a , b ) ) = Θ ( log ⁡ a − log ⁡ gcd ⁡ ( a , b ) ) Θ(\log \frac a{\gcd(a,b)})=Θ(\log a−\log \gcd(a,b)) Θ(loggcd(a,b)a​)=Θ(loga−loggcd(a,b))。   我们进行递推的时候，复杂度裂项相消就得到了 Θ ( k + log ⁡ a ) Θ(k+\log a) Θ(k+loga)。

  引理 2：对于一个数列 n n n，前缀 gcd ⁡ \gcd gcd 的连续段有最多 ⌊ log ⁡ 2 a ⌋ + 1 \lfloor \log_2a \rfloor+1 ⌊log2​a⌋+1 个。   由于前缀 gcd ⁡ \gcd gcd 如果有变化则至少除以 2 2 2，得证。

  从一个点出发每次往一个方向走的时候，肯定是走到 gcd ⁡ \gcd gcd 变了才停（不然没意义），或者是走到边界。左右都只有 log ⁡ a i \log a_i logai​ 段，因此从一个点出发的区间 dp 的复杂度就是 O ( n log ⁡ 2 a ) O(n \log^2 a) O(nlog2a) 了。   然后求 gcd ⁡ \gcd gcd 的时候注意往引理 1 上套。（一开始先 ST 表预处理区间 gcd ⁡ \gcd gcd，然后求出每一段的 gcd ⁡ \gcd gcd，然后基于正确的顺序合并区间）

  然后又要注意到，对于 [ l , r ] [l,r] [l,r]，如果 r r r 不是从 l l l 出发的变化点， l l l 也不是从 r r r 出发的变化点，那么 [ l , r ] [l,r] [l,r] 的 dp 也是没有意义的。（因为必先走到 [ l , r − 1 ] [l,r-1] [l,r−1] 或 [ l + 1 , r ] [l+1,r] [l+1,r]，这样的话在 [ l , r ] [l,r] [l,r] 停下来是没有意义的。）   因此有用的区间的总量就是 O ( n log ⁡ a ) O(n \log a) O(nloga) 的了，基于这个做 dp 就是 O ( n log ⁡ a ) O(n \log a) O(nloga) 的了。

  实现的一些方法：一开始先预处理出所有的区间（利用一个性质：设 L i L_i Li​ 为 i i i 的左变化点集合，那么 L i + 1 ⊂ L i ∪ { i + 1 } L_{i+1} \subset L_i \cup \{i+1\} Li+1​⊂Li​∪{i+1}，右边同理）。按区间长度从小到大 dp，找到左端点的上一个区间，和右端点的上一个区间，进行转移。排序要用基数排序，有 1 0 7 10^7 107 个区间。

\\   （为啥把思路整理一遍，就像把题解抄了一遍一样 qaq）