#思路 考虑动态规划设计状态为dp[i][j],前i个元素分成j个组的最大gcd之和，使用st表预处理方便o(logn)查询区间gcd，初始状态 dp[0][0] = 0，表示不使用任何元素且不分组的情况，对于 dp[i][j]，我们需要找到第 j 组的起始位置 k，并将前 k-1 个元素分成 j-1 组，使得 GCD 之和最大化，将 dp[i][j]更新为dp[k-1][j-1]+get_gcd(k, i)和dp[i][j]的最大值即可.

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;

// 辗转相除法求 GCD
int gcd(int a, int b) {

题目内容

塔塔拿到了一个长度为$n$的数组$a_i$，请你在不改变元素原有顺序的情况下将其分成恰好$m$个非空子数组，

对$m$个子数组分别计算数组内所有元素的$gcd$值，请问这$m$个非空子数组内部的$gcd$值之和的最大值是多

最大公约数($gcd$) 指能够整除多个非零整数的最大正整数。

分割指的是将数组分成若干个连续的子数组，每个元素都必须分到一个子数组中，且子数组之间不能有

重叠部分，子数组的并集要能够完全覆盖整个数组。

输入描述

第一行两个整数表示$n,m$。

第二行n个整数表示数组$a_i$。 $1≤m≤n≤400,1≤a≤100000$。

输出描述

输出一行一个整数表示答案.

样例1

输入

4 2
5 6 3 2

输出

6