#P1890. gcd区间

gcd区间

题目描述

给定 nn 个正整数 a1,a2,,ana_1,a_2,\dots,a_n

mm 次询问,每次询问给定一个区间 [l,r][l,r],输出 al,al+1,,ara_l,a_{l+1},\dots,a_r 的最大公因数。

输入格式

第一行两个整数 n,mn,m
第二行 nn 个整数表示 a1,a2,,ana_1,a_2,\dots,a_n
以下 mm 行,每行两个整数 l,rl, r 表示询问区间的左右端点。

输出格式

mm 行,每行表示一个询问的答案。

5 3
4 12 3 6 7
1 3
2 3
5 5

1
3
7

提示

  • 对于 30%30\% 的数据,1n1001\leq n \leq 1001m101\leq m \leq 10
  • 对于 60%60\% 的数据,1m10001\leq m \leq 1000
  • 对于 100%100\% 的数据,1lrn10001 \leq l \leq r \leq n \leq 10001m1061\leq m \leq 10^61ai1091 \leq a_i \leq 10^9