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

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

4.2 样例输出 #1

1
3
7

5 提示

• $1\le l\le r\le n\le 1000$，$1\le m\le {10}^6$，$1\le a_i\le {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';
}