题解 | 细胞增殖

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        int M = in.nextInt();

        Map<Long, Integer> freq = new HashMap<>();
        long maxNum = 0;

        for (int i = 0; i < N; i++) {
            long v = in.nextLong();
            freq.put(v, freq.getOrDefault(v, 0) + 1);
            maxNum = Math.max(maxNum, v);
        }

        while (M-- > 0) {
            int B = in.nextInt();
            int S = in.nextInt();

            int total = 0;
            int peak = 0;

            if (B == 0) {
                total = freq.getOrDefault((long) S, 0);
                peak = total;
            }
            else if (B == 1) {
                total = freq.getOrDefault((long) S + 1, 0);
                peak = total;
            }
            else {
                long cur = B;
                long limit = maxNum - S;

                while (cur <= limit) {
                    long target = cur + S;
                    Integer cnt = freq.get(target);
                    if (cnt != null) {
                        total += cnt;
                        peak = Math.max(peak, cnt);
                    }

                    if (cur > Long.MAX_VALUE / B) {
                        break;
                    }
                    cur *= B;
                }
            }

            System.out.println(total + " " + peak);
        }
    }
}

不能使用常规的循环遍历，必会超时