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