#P14925. [UJGOI 2021]GCD查询

    ID: 14141 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000数论筛法数据结构树状数组枚举分块线段树

[UJGOI 2021]GCD查询

题目描述

给定一个长度为 nn 的非负整数数组,以及 mm 个询问。每个询问由两个数 ll 和 rr 组成。

对于每个询问,请求出子数组 [l,r][l,r] 中所有两两最大公约数的最大值,也就是:

max⁡l≤i<j≤rgcd⁡(ai,aj)\max_{l \le i < j \le r} \gcd(a_i,a_j)

输入格式

第一行包含一个整数 nn(2≤n≤2⋅1052 \le n \le 2 \cdot 10^5),表示数组大小。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤1061 \le a_i \le 10^6),表示数组元素。

第三行包含一个整数 mm(1≤m≤2⋅1051 \le m \le 2 \cdot 10^5),表示询问个数。

接下来 mm 行,第 ii 行包含两个整数 li,ril_i,r_i(1≤li<ri≤n1 \le l_i < r_i \le n),表示询问区间的边界。

输出格式

对于每个询问,输出一个整数,表示该询问的答案。

输入

3
2 3 6
3
1 2
2 3
1 3

输出

1
3
3

计分方式

  1. (1212 分)m,n,ai≤200m,n,a_i \le 200;
  2. (77 分)m,n≤200m,n \le 200;
  3. (1717 分)ai≤50a_i \le 50;
  4. (77 分)所有 aia_i 都是 22 的幂;
  5. (2727 分)m,n≤15000m,n \le 15000;
  6. (1313 分)m,n≤35000m,n \le 35000;
  7. (1717 分)无额外限制。