算法第一道

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

输入描述

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

输出描述

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

/**
 * 对于m来说如果该数字本身为素数则直接输出就可以，如果本身不是素数，则在素数中找到一个可以除尽的数字便可以啦
 * 从第一个质数2开始遍历，直到遍历到n的平方根，如果n能被这个质数整除
 * 那么这个质数就是n的一个因子，输出这个质数即可。
 * 此时输出的这个质数也就是素数即为对应的m
 * @param args
 */
public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
    int k=scanner.nextInt();
    while (k-->0){
        int n=scanner.nextInt();
        boolean isPrime=true;
        for (int i=2;i<=Math.sqrt(n);i++){
            if(k%i==0){
                System.out.println(i);
                isPrime=false;
                break;
            }
        }
        if(isPrime=true){
            System.out.println(n);
        }
    }
}

算法第二道

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

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

输入描述

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

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

输出描述

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

public class Main2 {


    /**
     * 使得极差最小，只有两种情况
     * 1.几个数可以除尽，那么只需要计算小于平均值那一部分和平均数的差值加到一起就得到了（大于平均数的一样，因为每次取出两个数进行分别加减）
     * 2，几个数不可以除尽，则可以令其中几个为平均数（向下取整），另外几个为平均数+1
     * 由此可以得到最小极差只能有0或者1
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n + 1];
        long sum = 0;
        for (int i = 1; i <= n; ++i) {
            a[i] = scanner.nextInt();
            sum += a[i];
        }
        long ans = 0;
        long ave = sum / n;
        // 如果平均值刚好是整数，那么直接计算
        if (ave * n == sum) {
            for (int i = 1; i <= n; ++i) {
                //大于的跟小于的肯定是相等的。取其中的一部分就好啦
                if (a[i] < ave) {
                    ans += ave - a[i];
                }
            }
        } else {
            int cnt = (int) (sum - ave * n);
            cnt = n - cnt;
            Arrays.sort(a, 1, n + 1);
            for (int i = 1; i <= n; ++i) {
                if (i <= cnt && a[i] < ave) {
                    ans += ave - a[i];
                } else if (i > cnt && a[i] < ave + 1) {
                    ans += ave + 1 - a[i];
                }
            }
        }
        System.out.println(ans);
    }
}

算法第三道

小美和小团在玩一个游戏，游戏中有一个长度为 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)代表数组,

输出描述

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

第三题不太会，大佬们有什么好的思路吗