QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 128 MB Total points: 100

# 7470. WBLT

统计

题目描述

给你一个长为 $n$ 的序列,有 $m$ 次查询操作。

每次查询操作给定参数 $l,r,b$,需输出最大的 $x$,使得存在一个 $a$,满足 $0\leq a< b$,使得 $a,a+b,a+2b,\ldots,a+(x-1)b$ 都在区间 $[l,r]$ 内至少出现过一次。

如果不存在 $[0,b-1]$ 内的数,则输出 $0$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数表示这个序列。

第三行一个整数 $m$。

之后 $m$ 行,每行三个整数 $l,r,b$,表示一次查询操作。

输出格式

对于每个查询操作,输出一行一个整数表示答案。

样例 #1

样例输入 #1

6
1 1 4 5 1 4
3
1 6 1
2 3 3
3 4 1

样例输出 #1

0
2
0

提示

Idea:nzhtl1477,Solution:nzhtl1477,Code:ccz181078,Data:ccz181078&Forever_Pursuit

对于 $30\%$ 的数据,所有出现过的数在 $[0,1000]$ 之间。

对于另外 $30\%$ 的数据,$b \leq 1000$。

对于 $100\%$ 的数据,所有出现过的数在 $[0,10^5]$ 之间。