解题思路

1. 先用哈希表统计数组每个值出现次数 freq[v]（数组已排序但不影响，用哈希更快）。

2. 对每个询问：

   • 若 (x=0)：(0^K=0)（(K>=1)），所以只可能是 (a=y) 总数=峰值=freq[y]

   • 若 (x=1)：(1^K=1)，所以只可能是 (a=y+1) 总数=峰值=freq[y+1]

   • 若 (x>=2)：(x^K) 严格递增，只需枚举 (K=1,2,3......)，不断乘 (x) 得到幂 p：

     • 若 p + y > maxA 则停止（maxA 为数组最大值）
     • 累加 freq[p+y]，并更新峰值
     • 下一次令 p *= x，注意用“乘前判断”避免溢出：若 p > (maxA - y) / x 则下一次会超界，直接停

相关算法：哈希表计数、幂次枚举（指数增长）、溢出/上界剪枝。

复杂度分析

• 预处理建表：时间 (O(n))，空间 (O(n))（按不同值计数）。

• 每次询问：

  • $(x\in{0,1})$ 为 $(O(1))$
  • $(x\ge2)$ 枚举次数约为 $(\lfloor \log_x(maxA-y)\rfloor + 1)$，最坏在 $(x=2)$ 时约 $34$ 次（因为 ($a[i]\le 10^{10})$）

• 总体时间：$(O(n + m\log maxA))$，本题约 $(O(n + 34m))$，可通过。

• 总体空间：$(O(n))$

代码实现

Python

import sys

# 功能函数：返回每个询问的(总数, 峰值)
def solve(a, queries):
    freq = {}
    for v in a:
        freq[v] = freq.get(v, 0) + 1
    maxA = a[-1]

    ans = []
    for x, y in queries:
        # x=0: 0^K=0(K>=1)，只可能等于y
        if x == 0:
            c = freq.get(y, 0)
            ans.append((c, c))
            continue

        # x=1: 1^K=1
        if x == 1:
            c = freq.get(y + 1, 0)
            ans.append((c, c))
            continue

        # x>=2：枚举幂 p=x^K
        total = 0
        peak = 0
        limit = maxA - y  # 需要 p <= limit
        if limit < 0:
            ans.append((0, 0))
            continue

        p = x  # K=1
        while p <= limit:
            v = p + y
            c = freq.get(v, 0)
            if c:
                total += c
                if c > peak:
                    peak = c

            # 乘前判断，避免溢出/无意义循环
            if p > limit // x:
                break
            p *= x

        ans.append((total, peak))
    return ans

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    queries = [tuple(map(int, input().split())) for _ in range(m)]
    res = solve(a, queries)
    sys.stdout.write("\n".join(f"{t} {p}" for t, p in res))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {

    // 功能函数：处理所有询问，返回二维数组 ans[i][0]=总数, ans[i][1]=峰值
    static long[][] solve(long[] a, int[] xs, int[] ys) {
        HashMap<Long, Integer> freq = new HashMap<>(a.length * 2);
        for (long v : a) freq.put(v, freq.getOrDefault(v, 0) + 1);
        long maxA = a[a.length - 1];

        int m = xs.length;
        long[][] ans = new long[m][2];

        for (int i = 0; i < m; i++) {
            int x = xs[i];
            long y = ys[i];

            if (x == 0) { // 0^K=0
                int c = freq.getOrDefault(y, 0);
                ans[i][0] = c;
                ans[i][1] = c;
                continue;
            }

            if (x == 1) { // 1^K=1
                int c = freq.getOrDefault(y + 1, 0);
                ans[i][0] = c;
                ans[i][1] = c;
                continue;
            }

            long limit = maxA - y; // 需要 p<=limit
            if (limit < 0) {
                ans[i][0] = 0;
                ans[i][1] = 0;
                continue;
            }

            long total = 0;
            int peak = 0;

            long p = x; // K=1
            while (p <= limit) {
                long v = p + y;
                Integer c = freq.get(v);
                if (c != null) {
                    total += c;
                    if (c > peak) peak = c;
                }

                // 乘前判断，避免溢出/越界
                if (p > limit / x) break;
                p *= x;
            }

            ans[i][0] = total;
            ans[i][1] = peak;
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(new BufferedInputStream(System.in));
        int n = fs.nextInt();
        int m = fs.nextInt();

        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = fs.nextLong();

        int[] xs = new int[m];
        int[] ys = new int[m];
        for (int i = 0; i < m; i++) {
            xs[i] = fs.nextInt();
            ys[i] = fs.nextInt();
        }

        long[][] ans = solve(a, xs, ys);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            sb.append(ans[i][0]).append(' ').append(ans[i][1]).append('\n');
        }
        System.out.print(sb.toString());
    }

    // 简洁输入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { in = is; }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        long nextLong() throws IOException {
            int c;
            do c = read(); while (c <= ' ' && c != -1);
            long sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            long x = 0;
            while (c > ' ') {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sign;
        }

        int nextInt() throws IOException { return (int) nextLong(); }
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 功能函数：处理所有询问，返回(总数, 峰值)
static vector<pair<long long,int>> solve(const vector<long long>& a,
                                        const vector<int>& xs,
                                        const vector<int>& ys) {
    unordered_map<long long,int> freq;
    freq.reserve(a.size() * 2);
    for (auto v : a) freq[v]++;

    long long maxA = a.back();
    int m = (int)xs.size();
    vector<pair<long long,int>> ans(m);

    for (int i = 0; i < m; i++) {
        int x = xs[i];
        long long y = ys[i];

        if (x == 0) { // 0^K=0
            int c = freq.count(y) ? freq[y] : 0;
            ans[i] = {c, c};
            continue;
        }
        if (x == 1) { // 1^K=1
            long long v = y + 1;
            int c = freq.count(v) ? freq[v] : 0;
            ans[i] = {c, c};
            continue;
        }

        long long limit = maxA - y; // 需要 p<=limit
        if (limit < 0) {
            ans[i] = {0, 0};
            continue;
        }

        long long total = 0;
        int peak = 0;

        long long p = x; // K=1
        while (p <= limit) {
            long long v = p + y;
            auto it = freq.find(v);
            if (it != freq.end()) {
                total += it->second;
                peak = max(peak, it->second);
            }

            // 乘前判断，避免溢出/越界
            if (p > limit / x) break;
            p *= x;
        }

        ans[i] = {total, peak};
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> xs(m), ys(m);
    for (int i = 0; i < m; i++) cin >> xs[i] >> ys[i];

    auto ans = solve(a, xs, ys);
    for (auto &p : ans) {
        cout << p.first << ' ' << p.second << "\n";
    }
    return 0;
}

题目内容

服务器常用指数退避策略来避免网络拥塞，每次访问失败后，会大间隔间隔成倍后再访问，下次重试的间隔在最大间隔内随机化。小华作为测试人员模拟了一些输入，服务器后台可看到$n$个访问时间点，第$i$个为$a[i]$(其中$a[i]$值可能重复)。现在他想知道对于一个数对$(x[j],y[j])$，满足$a[i] = (x[j])^K + y[j]$的访问一共有多少个，峰值是多少?

注:$K$看可取任意正整数，峰值指K取某一整数时满足$a[i] =(x[j])^K+y[j]$的数量的最大访问个数。

输入描述

第$1$行两个整数$n,m$，用空格隔开。表示有$n$个数，$m$次询问$(1<=n<=100000,1 <= m <=200000)$。

第$2$行有$n$个数，用空格隔开，第$i$个数为$a[i] (1<=i <= n,1 <= a[i] <=1000000000)$，从小到大排序。

从第$3$行到第$m+2$行，每行两个整数，用空格隔开，表示给定一个整数数对$(x[j],y[j]) (0 <= x[i],y[j] <=10000000)$

输出描述

$m$行，每行两个数，第$j$行回答询问对于$(x[j],y[j])$，可满足$a[i] =(x[j])^K + y[j]$($K$取任意正整数)的数量一共有多少个，峰值为多少，用空格隔开。

样例1

输入

4 2
45 78 90 429981774
12 78 
9 42561285

输出

2 1 
1 1

说明

对于第一组询问,要满足$a[1]=12^K+78$，当$K$取$1.8$时$12^1+78=90=a[3]$，此时刻有1个访问。

$12^8+78=429981774=a[4]$，此时刻有1个访问。因此一共2个，峰值为1。

对于第二组询问,要满足$a[i]=9^K+42561285$，当$K$取$9$时$9^9+42561285 =429981774=a[4]$。因此一共1个，峰值为1。

样例2

输入

11 3
2 3 4 5 5 6 7 7 9 16 17
2 0
2 1
0 7

输出

3 1 
5 2
2 2

说明

对于第一组询问要满足$a[1]=2^K+0$,当$K$取$1,2,4$时:

$2^1+0=2=a[1]$,此时刻有1个访问

$2^2+0=4=a[3]$,此时刻有1个访问

$2^4+0=16=a[10]$,此时刻有1个访问

因此一共$3$个,蜂值为$1$。

对于第二组询问,要满足$a[1]=2^K+1$的$a[1]$,当$K$取1$,2,3,4$时:

$2^1+1=3=a[2]$,此时刻有$1$个访问

$2^2+1=5=a[4]=2[5]$,此时剪有$2$个访问

$2^3+1=9=[9]$,此时充有$1$个访问

$2^4+1=17= a[11]$，此时完有$1$个访问

因此一共$5$个,峰值为$2$

对于第三组询问要满足$a(1)=0^K+7$的a抑,值只能为$7$。$a[7]=a[8]=7$,有两个数满足因此一共$2$个,峰值为$2$