1. 题目

传送门= ̄ω ̄=
题目描述

给定一行n个正整数a[1]..a[n]。

m次询问,每次询问给定一个区间[L,R],输出a[L]..a[R]的最大公因数。
输入输出格式
输入格式:

第一行两个整数n,m。

第二行n个整数表示a[1]..a[n]。

以下m行,每行2个整数表示询问区间的左右端点。

保证输入数据合法。

输出格式:

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

输入输出样例
输入样例#1:

输出样例#1:

说明

对于30%的数据,n <= 100, m <= 10

对于60%的数据,m <= 1000

对于100%的数据,1 <= n <= 1000,1 <= m <= 1,000,000

2. 思路

数据范围:1000,直接枚举,预处理f[i][j]。f[i][j]指区间[i,j]的最大公约数,递推式为:

这应该很明显吧!O(∩_∩)O~

代码: