#P1890. gcd区间
gcd区间
题目描述
给定 个正整数 。
次询问,每次询问给定一个区间 ,输出 的最大公因数。
输入格式
第一行两个整数 。
第二行 个整数表示 。
以下 行,每行两个整数 表示询问区间的左右端点。
输出格式
共 行,每行表示一个询问的答案。
5 3
4 12 3 6 7
1 3
2 3
5 5
1
3
7
提示
- 对于 的数据,,;
- 对于 的数据,;
- 对于 的数据,,,。
给定 n 个正整数 a1,a2,…,an。
m 次询问,每次询问给定一个区间 [l,r],输出 al,al+1,…,ar 的最大公因数。
第一行两个整数 n,m。
第二行 n 个整数表示 a1,a2,…,an。
以下 m 行,每行两个整数 l,r 表示询问区间的左右端点。
共 m 行,每行表示一个询问的答案。
5 3
4 12 3 6 7
1 3
2 3
5 5
1
3
7