蓝桥杯2023年第十四届省赛真题-公因数匹配 java

解题思路:

 找出每个数的质因子用map存起来，key存质因子，val则是存储最小下标。
 后续如果发现相同的质因子，则枚举该数字出现的质因子找最小下标 
参考代码:

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int Inf = 0x7fffffff;

    public static void main(String[] args) throws IOException {
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        int l = Inf, r = Inf;
        for (int i = 1; i <= n; i++) {
            List<Integer> list = new ArrayList<>();
            int m = a[i];
            for (int j = 2; j <= m / j; j++) {
                if (m % j == 0) {
                    while (m % j == 0) {
                        m /= j;
                    }
                    if (!map.containsKey(j)) {
                        map.put(j, i);
                    } else {
                        map.put(j, Math.min(map.get(j), i));
                        list.add(j);
                    }
                }
            }
            if (m > 1) {
                if (!map.containsKey(m)) {
                    map.put(m, i);
                } else {
                    map.put(m, Math.min(map.get(m), i));
                    list.add(m);
                }
            }
            if (!list.isEmpty()) {
                for (int x : list) {
                    int val = map.get(x);
                    if (l > val) {
                        l = val;
                        r = i;
                    }
                }
            }
        }
        out.println(l + " " + r);
        out.close();
    }

    static class sc {
        private static final StreamTokenizer input = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public static int nextInt() throws IOException {
            input.nextToken();
            return (int) input.nval;
        }
    }
}