题目描述
给定由 n 个两两互质的正整数组成的序列 a1,a2,…,an。
每次询问给出 l,r,p,q。从区间 [l,r] 选择下标 i,j,求以下值的最大值。
$$\gcd\left(\left|a_i^p-a_j^p\right|,\left|a_i^q-a_j^q\right|\right)$$
先比较未取模的值,求出最大值后,再输出它对 19970402 取模的结果。
输入格式
首先读入整数 n,接下来读入 n 个整数 a1,a2,…,an。
接下来读入整数 m,表示询问次数。随后 m 行,每行四个整数 l,r,p,q。
输出格式
输出 m 行,每行是一次询问的答案。
样例
3
2 5 9
2
1 2 2 3
2 3 4 6
3
56
两次询问的最大值分别为 gcd(25−4,125−8)=3 与 gcd(6561−625,531441−15625)=56。
数据范围
- 对于 20% 的数据,n≤10,m≤100,1≤p,q≤10,1≤ai≤20。
- 另有 20% 的数据满足 p=q。
- 对于所有数据,1≤n,m≤105,1≤l<r≤n,1≤p,q,ai≤109。
原 PDF 题面