3771: 求余来喽(第四轮01)
题目描述
白浅妹妹今天学习了求余，她已经学会了，但是老师还是给了她 n 个数字让她练习求余。 但是老师只给了 n 个被除数，并没有说除数是几，只说除数的范围是 [l, r]。白浅妹妹决定 自己设置除数，于是她从 [l, r] 中选择了一个正整数 k，然后对每一个数字都对 k 求余，得 到了 n 个新的数字。
白浅妹妹希望 n 个新的数字之和尽可能小， 于是她想问问你应该如何设置 k，如果有多种 可能的答案，请输出最小的那一个。
文件样例：sample.zip
输入
输入第一行包含三个正整数 n, l, r，意义如题面所示。
接下来一行包含 n 个正整数，其中第 i 个正整数为 ai (1 ≤ ai ≤ 4000)。
输出
输出一行一个整数表示答案。
样例输入 复制
1 20 1000
1002样例输出 复制
167提示
【样例 1 输入】
1 20 1000
1002
【样例 1 输出】
167
【说明】
虽然设置成 334 也可以让求余结果为 0，但是题目要求输出最小的 k，所以输出 167。
【样例 2 输入】
3 7 8
21 22 23
【样例 2 输出】
7
【说明】
将 k 设置为 7，则三个数字对 7 求余的结果分别是 0， 1， 2， 求和得到 3。设置为 8 的
话， 三个数字对 8 求余的结果分别是 5， 6， 7， 求和得到 18 。3 更小， 所以输出 7 表示 将 k设置为 7。
【备注】
对于 1 — 2 测试点，有 l = 1
对于 3 — 4 测试点，有 l = r
对于 5 — 6 测试点，有 ai < l
对于 7 — 8 测试点，有 n = 1
对于 9 — 10 测试点，有 1 ≤ l ≤ r ≤ 3000, 1 ≤ n ≤ 3000