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\) |
「scoj2020」Round 1
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 4
- 开始于
- 2021-07-01 08:30
- 结束于
- 2021-07-02 22:30
- 持续时间
- 38.0 小时
- 主持人
- 参赛人数
- 2