#P10761. 澳洲猴

    ID: 9879 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 5 上传者: 标签>CF1800普及+/提高-欧几里得算法普通线段树快速幂

澳洲猴

题目描述

给定由 nn 个两两互质的正整数组成的序列 a1,a2,…,ana_1,a_2,\ldots,a_n。

每次询问给出 l,r,p,ql,r,p,q。从区间 [l,r][l,r] 选择下标 i,ji,j,求以下值的最大值。

$$\gcd\left(\left|a_i^p-a_j^p\right|,\left|a_i^q-a_j^q\right|\right)$$

先比较未取模的值,求出最大值后,再输出它对 1997040219970402 取模的结果。

输入格式

首先读入整数 nn,接下来读入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

接下来读入整数 mm,表示询问次数。随后 mm 行,每行四个整数 l,r,p,ql,r,p,q。

输出格式

输出 mm 行,每行是一次询问的答案。

样例

3
2 5 9
2
1 2 2 3
2 3 4 6
3
56

两次询问的最大值分别为 gcd⁡(25−4,125−8)=3\gcd(25-4,125-8)=3 与 gcd⁡(6561−625,531441−15625)=56\gcd(6561-625,531441-15625)=56。

数据范围

  • 对于 20%20\% 的数据,n≤10n\le10,m≤100m\le100,1≤p,q≤101\le p,q\le10,1≤ai≤201\le a_i\le20。
  • 另有 20%20\% 的数据满足 p=qp=q。
  • 对于所有数据,1≤n,m≤1051\le n,m\le10^5,1≤l<r≤n1\le l<r\le n,1≤p,q,ai≤1091\le p,q,a_i\le10^9。

原 PDF 题面