设 dp[i][j]dp[i][j]dp[i][j] 表示前 iii 段岩芯分成 jjj 组时，gcd\mathrm{gcd}gcd 之和的最大值。转移枚举第 jjj 组的起点 kkk：
其中 j=1j=1j=1 且 k=1k=1k=1 时直接取整段 gcd\mathrm{gcd}gcd。
地质队沿钻孔依次取得 nnn 段岩芯，第 iii 段的矿物指数为 aia_iai。实验室要把整列岩芯送去分组化验，但必须保持取样先后顺序，不能打乱、不能漏段。化验规程要求恰好划成 mmm 个非空连续段，并以各段内部指数的最大公因数之和作为这套划分的得分，实验室希望得分尽可能大。划分必须连续、非空、互不相交，并集恰好覆盖整列。最大公因数 gcd\mathrm{gcd}gcd 指能够整除若干正整数的最大正整数。
约束：1≤m≤n≤4×1021 \le m \le n \le 4 \times 10^21≤m≤n≤4×102，1≤ai≤1051 \le a_i \le 10^51≤ai≤105。
第一行两个整数 nnn 和 mmm，分别表示岩芯段数与要分成的组数。
本题属于以下题库，请选择所需题库进行购买
Scan the QR code below with WeChat to sign in
设置一个用户名，下一步用微信扫码完成注册
请使用微信扫描下方二维码完成注册
