2024美团秋招笔试0818

1

小美对 gcd (最大公约数)很感兴趣，她会询问你t次。每次询问给出一个大于1的正整数n，你是否找到一个数字m(2≤m≤n)，使得 gcd(n,m)为素数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数T($1<T<100$)代表数据组数，每组测试数据描述如下:在一行上输入一个整数 n ($2<n<105$)代表给定的数字

输出描述

对于每一组测试数据，在一行上输出一个整数，代表数字 m如果有多种合法答案，您可以输出任意一种。

测试用例：2 114 15

输出：4 5

思路：暴力+gcd+判断素数

2

小美有一个长度为 n 的数组，每次操作可以选择两个下标之和 j，将 $a_i$减去1，将 $a_j$加上 1。小美想知道最少需要多少次操作，可以使数组极差最小、

数组的极差为数组中最大值和最小的差

输入描述

第一行输入一个整数 n(2 < n < 105)代表数组的长度.

第二行输入 几 个整数 a1,a2,·..,an(1 ≤ a¡≤ 10°)代表数组的元素

输出描述

在一行上输出一个整数，表示最少需要多少次操作

测试用例：1 2 3 4 5

输出：3

3 3 3 3 3

思路：题目要求极值最小，只有两种可能，即0或1，因此只需关注将大值减到a+1，小值加到a 假设数组n个元素，和为sum，sum / n = a

• 当sum % n = 0 时，极值最小可以达到0，这时只需要计算 值小于a 的元素全部加到a的和sum1
• 当sum % n = b 时，极值为1，小于a的元素全部加到a的和为sum1，但这时还多了b，b不一定均匀分布在b个元素中，所以需要统计将所有大于a+1的值减到a+1的和sum2。如果sum2 < sum1，说明小值符合要求后，大值全部能够符合要求，返回sum1；否则返回sum2

3

小美和小团在玩一个游戏，游戏中有一个长度为 n 的数组 a1,a2,..,an 和一个固定的整数k。

游戏规则如下，双方都会执行最优策略:

第一步，小美选择一个非空的区间[l,r]，将这个区间中的所有数字都乘上k。

第二步，小团选择一个非空的区间[l,r]，将这个区间中的所有数字都乘上k。

记 sum =》 a:，小美想要让 sum 尽可能大，小团想让sum尽可能小,你需要求出最后 sum 的值。

输入描述

第一行输入两个整数n和k$(1 ≤n≤ 1000;-105<k< 105)$代表数组长度和固定的整数。

第二行输入 几 个整数 a1,Q2,·..,an(一105 < a¡< 105)代表数组,

输出描述

在一行上输出一个整数表示答案。