D. 修改序列(gcd)
暂无测试数据。
Description
下课了,老师离开了教室,\(\text{Scarral}\) 决定修改黑板上的式子,这样当老师下节课算的时候就会非常麻烦(恶搞qwq
原来黑板上有一个由 \(n\) 个数字成的序列 \(A\),定义了一个函数如下:
\[f(x) = \sum_{i=1}^{x-1}\sum_{j=i+1}^x\gcd(A_i,A_j)\]
由于下课的时间比较短,\(\text{Scarral}\) 只能将其中至多 \(k\) 个数改为 \([L,R]\) 区间内的任一整数。为了使老师算得最麻烦,\(\text{Scarral}\) 决定最大化 \(f(n)\),现在 \(\text{Scarral}\) 想知道修改后 \(f(n)\) 的最大值是多少。
Input
第 \(1\) 行 \(4\) 个正整数,分别表示 \(n\),\(k\),\(L\) 和 \(R\)。
第 \(2\) 行 \(n\) 个正整数,第 \(i\) 个正整数表示 \(A_i\)。
Output
经过至多 \(k\) 次修改后的最大值。
Sample
Sample input
待填坑
Sample output
待填坑
Hint
本题共 \(10\) 个测试点。
测试点 | \(n\le\) | \(k\le\) | \(L,R\le\) |
---|---|---|---|
\(1\)~\(5\) | \(100\) | \(10\) | \(1000\) |
\(6\)~\(10\) | \(10^5\) | \(40\) | \(10^9\) |