题目内容

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

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

#思路 考虑动态规划设计状态为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) {