1 P1890 gcd区间 - 洛谷

1 题目描述

给定 \(n\) 个正整数 \(a_1,a_2,\dots,a_n\)。

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

2 输入格式

第一行两个整数 \(n,m\)。
第二行 \(n\) 个整数表示 \(a_1,a_2,\dots,a_n\)。
以下 \(m\) 行，每行两个整数 \(l, r\) 表示询问区间的左右端点。

3 输出格式

共 \(m\) 行，每行表示一个询问的答案。

4 样例 #1

4.1 样例输入 #1

4.2 样例输出 #1

1
2
3

1
3
7

5 提示

\(1 \leq l \leq r \leq n \leq 1000\)，\(1\leq m \leq 10^6\)，\(1 \leq a_i \leq 10^9\)。

首先，对于 \(i=j\) 的情况，显然有 \(F[i][j]=a[i]\)。

然后，对于 \(i<j\) 的情况，我们可以递推得到 \(F[i][j]\) 的值。具体地，我们可以根据 \(F[i][i]\) 和 \(F[i+1][j]\) 的值来计算 \(F[i][j]\).

动态转移方程：\(f[i,j] = \gcd (f[i,i], f[i + 1,j])\). ## 6 代码

#include <bits/stdc++.h>
using namespace std;
int n, m, f[1010][1010], l, r;
int main()
{
    ios::sync_with_stdio(0),cin.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> f[i][i];
    for (int i = n-1; i >=1; i--)
        for (int j = i+1; j <= n; j++)
            f[i][j] = __gcd(f[i][i], f[i + 1][j]);
    while (m--) cin >> l >> r,cout << f[l][r] << '\n';
}