#P18176. Max GCD
Max GCD
Max GCD
给定一个长度为 的正整数数组 ,下标从 1 开始。定义区间 的价值为
$$\max_{\substack{l\le i<j<k\le r\\j-i\le k-j}} \gcd(a_i,a_j,a_k).$$也就是说,需要选择三个不同下标,满足左边两个下标的距离不大于右边两个下标的距离,求三数最大公约数的最大值。距离相等允许;这三个位置不要求连续。
如果区间中不足三个元素,即 ,定义价值为 0。
给出 个询问,每个询问要求计算一个区间的价值。数组不会修改。
输入格式
第一行两个整数 ,满足 、。
第二行 个整数 ,满足 。
接下来 行,每行两个整数 ,满足 ,表示一个询问。
输出格式
对每个询问输出一行一个整数,表示对应区间的价值。答案不取模。
样例
输入:
8 8
8 24 4 6 6 7 3 3
1 5
2 6
3 7
5 8
4 8
1 3
2 5
3 8
输出:
4
2
3
1
3
4
2
3