3767: 减法和求余(第三轮01)
题目描述
鸡尾酒的学生丹丹永远分不清减法和求余，他觉得两种运算都是将数字变小，所以差不多。
于是鸡尾酒给了他两道题目来帮助他分清这两种运算。第一道题目是这样的：给定一个包含 n 个数字的数组，每次你可以任选两个数字做减法运算，将这两个数字变成一个新数字放回 数组，经过 n − 1 次操作之后变成一个数字。你的目标是让最终的这一个数字变得尽可能 大，请问最大是多少。
当然，这道题只涉及减法，于是鸡尾酒还有一道同样的题目（只有加粗的地方不同）：给定 一个包含 n 个数字的数组， 每次你可以任选两个数字做求余运算， 将这两个数字变成一个 新数字放回数组，经过 n − 1 次操作之后变成一个数字。你的目标是让最终的这一个数字 变得尽可能大，请问最大是多少。
丹丹说：“都是 n 个数字变成 1 个数字，这两道题不是一样吗？” 看来丹丹又分不清了，你能帮帮他吗？
为了防止丹丹搞混数字，所以鸡尾酒给出的 n 个数字各不相同。
输入
第一行输入一个正整数 n, k， 表示共有 n 个数字， k 是题目编号， 如果 k = 1， 则你需要 完成“减法”这道题， k = 2 表示你需要完成“求余”这道题。
接下来一行输入 n 个数字，其中第 i 个数字为 ai (1 ≤ ai ≤ 10^6)
输出
输出一行一个整数表示答案。
样例输入 复制
5 1
1 2 3 4 5样例输出 复制
13提示
【样例 1 输入】
5 1
1 2 3 4 5
【样例 1 输出】
13
【说明】
样例 1 的 k = 1，说明是一道减法问题，可以先用数组中的 1 减去 2，得到 −1，然后用 −1 减去 4，得到 −5，用 −5 减去 5，得到 −10，用 3 减去 −10，得到 13。
【样例 2 输入】
3 2
100 400 905
【样例 2 输出】
100
【说明】
样例 2 的 k = 2，说明是一道求余问题，先用 905 求余 400，得到余数 505，然后用 100 求余 505，得到余数 100。方案不唯一，但是无法得到比 100 还大的数字了。
【备注】
|
测试点编号 |
k |
n |
|
1 |
1 |
1 |
|
2 |
1 |
2 |
|
3 |
1 |
3 |
|
4 |
1 |
1000 |
|
5 |
1 |
100000 |
|
6 |
2 |
1 |
|
7 |
2 |
2 |
|
8 |
2 |
3 |
|
9 − 10 |
2 |
100000 |