KLOOK编程题0330

Given three positive integers a,b,c that satisfy the condition where a*b,a*c,b*c are all perfect squares,we call(a,b,c) a square triplet given a positive integer n ,find the number of square triplets(a,b,c) satisfying 1 ≤ a < b < c ≤ n
Input： a single line contain a positive integer n (1≤ n ≤ 2 * 10^5)
Output： output an integer representing the answer

利用数学性质：当三个数的任意两数乘积为平方数时，它们的无平方因子部分必须相同。

1. 数学性质：若 a*b 是平方数，则 a 和 b 的无平方因子部分必须相同。推广到三元组 (a,b,c) 时，三者必须共享同一无平方因子。
2. 预处理：计算每个数的无平方因子部分，并统计相同值的出现次数。
3. 组合计数：对每组相同无平方因子的数，计算组合数 C(k,3)。

public static int countSquareTriplets(int n) {
        if (n < 3) return 0;

        int[] lpf = getLPF(n); // 预处理最小质因数数组
        int[] squareFree = computeSquareFree(n, lpf); // 计算无平方因子数

        // 统计相同无平方因子数的频率
        Map<Integer, Integer> freq = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            freq.put(squareFree[i], freq.getOrDefault(squareFree[i], 0) + 1);
        }

        // 计算组合数 C(k,3)
        int result = 0;
        for (int count : freq.values()) {
            result += combination(count);
        }
        return result;
    }

    // 生成最小质因数数组（线性筛法）
    private static int[] getLPF(int max) {
        int[] lpf = new int[max + 1];
        for (int i = 2; i <= max; i++) {
            if (lpf[i] == 0) {
                lpf[i] = i;
                for (int j = 2 * i; j <= max; j += i) {
                    if (lpf[j] == 0) {
                        lpf[j] = i;
                    }
                }
            }
        }
        return lpf;
    }

    // 计算每个数的无平方因子部分
    private static int[] computeSquareFree(int n, int[] lpf) {
        int[] squareFree = new int[n + 1];
        squareFree[1] = 1;

        for (int i = 2; i <= n; i++) {
            int x = i;
            int m = 1;
            while (x > 1) {
                int p = lpf[x];
                int cnt = 0;
                while (x % p == 0) {
                    x /= p;
                    cnt++;
                }
                if (cnt % 2 != 0) {
                    m *= p;
                }
            }
            squareFree[i] = m;
        }
        return squareFree;
    }

    // 计算组合数 C(n,3)
    private static int combination(int n) {
        if (n < 3) return 0;
        return n * (n - 1) * (n - 2) / 6;
    }