P4534.第1题-指数退避

1000ms

Difficulty: 5

所属公司 : 华为

算法与标签>哈希表

题目内容

服务器常用指数退避策略来避免网络拥塞，每次访问失败后，会大间隔间隔成倍后再访问，下次重试的间隔在最大间隔内随机化。小华作为测试人员模拟了一些输入，服务器后台可看到 $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[i]=12^K+78$ ，当 $K$ 取 $1$ 时 $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[i]=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[i]=2^K+1$ 的 $a[i]$ ,当 $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[i]=0^K+7$ 的 $a[i]$ ,值只能为 $7$ 。 $a[7]=a[8]=7$ ,有两个数满足因此一共 $2$ 个,峰值为 $2$

输入

预期输出（选填）

解题思路

P4534.第1题-指数退避

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About