题解 | 小苯的数字权值

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        int[] queries = new int[T];
        int max_x = 0;
        for (int i = 0; i < T; i++) {
            queries[i] = scanner.nextInt();
            if (queries[i] > max_x) {
                max_x = queries[i];
            }
        }

        int[] divisors = new int[max_x + 1];
        for (int i = 1; i <= max_x; i++) {
            for (int j = i; j <= max_x; j += i) {
                divisors[j]++;
            }
        }

        int[] minPrime = new int[max_x + 1];
        for (int i = 2; i <= max_x; i++) {
            if (minPrime[i] == 0) {
                minPrime[i] = i;
                if ((long) i * i <= max_x) {
                    for (int j = i * i; j <= max_x; j += i) {
                        if (minPrime[j] == 0) {
                            minPrime[j] = i;
                        }
                    }
                }
            }
        }

        int[] k = new int[max_x + 1];
        for (int x = 2; x <= max_x; x++) {
            int temp = x;
            int currentK = 0;
            while (temp > 1) {
                int p = minPrime[temp];
                int cnt = 0;
                while (temp % p == 0) {
                    temp /= p;
                    cnt++;
                }
                currentK += cnt;
            }
            k[x] = currentK;
        }

        int[] maxVal = new int[max_x + 1];
        for (int x = 2; x <= max_x; x++) {
            maxVal[x] = Math.max(divisors[x], 2 * k[x]);
        }

        for (int q : queries) {
            System.out.println(maxVal[q]);
        }
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 预处理因子数目：使用筛法计算每个数的因子数目，存储在数组divisors中。
2. 预处理最小质因数：使用筛法找到每个数的最小质因数，存储在数组minPrime中。
3. 计算质因数指数之和：对于每个数，分解质因数并累加其所有质因数的指数，存储在数组k中。
4. 计算最大权值和：对于每个数，比较其因子数目和两倍质因数指数之和，取较大者作为结果，存储在数组maxVal中，并输出结果。