C++程序用于范围LCM查询

给定一个整数数组，计算LCM(l, r)形式的查询。可能有许多查询，因此需要有效地评估这些查询。

LCM（l，r）表示位于索引l和r之间的数组元素的LCM（包括两个索引）

数学上，
LCM（l，r）= LCM（arr[l]，arr[l + 1]，……，
arr [r-1]，arr [r]）

例子:

输入：数组= {5，7，5，2，10，12，11，17，14，1，44}
查询：LCM（2,5），LCM（5,10），LCM（0,10）
输出：60 15708 78540
说明：在第一个查询中，LCM（5，2，10，12）= 60，同样适用于其他查询。

一个简单的方法是遍历每个查询并使用以下公式计算答案，

LCM(a, b) = (a*b) / GCD(a,b)

然而，由于查询数可能很大，这种方法是不切实际的。

一种有效的解决方案是使用线段树。回想一下，在这种情况下，不需要更新，我们可以构建树一次，然后可以重复使用该树来回答查询。树中的每个节点应存储该特定段的LCM值，我们可以使用上述公式组合段。因此，我们可以有效地回答每个查询！

下面是相应的解决方案。

// 使用线段树来计算给定范围的LCM
#include <bits/stdc++.h>
using namespace std;
  
#define MAX 1000
  
// 为树分配空间
int tree[4*MAX];
  
// 全局声明数组
int arr[MAX];
  
// 求 a 和 b 的 gcd
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b%a, a);
}
  
//用于查找 LCM 的实用函数
int lcm(int a, int b)
{
    return a*b/gcd(a,b);
}
  
// 构建线段树的函数
// Node 是当前子树的开始索引，start 和 end 是全局数组中的索引
void build(int node, int start, int end)
{
    // 如果当前子数组中只有一个元素
    if (start==end)
    {
        tree[node] = arr[start];
        return;
    }
  
    int mid = (start+end)/2;
  
    // 构建左右段
    build(2*node, start, mid);
    build(2*node+1, mid+1, end);
  
    // 构建父节点
    int left_lcm = tree[2*node];
    int right_lcm = tree[2*node+1];
  
    tree[node] = lcm(left_lcm, right_lcm);
}
  
// 为数组范围(l, r)进行查询的函数
// Node 是当前段在线段树中的根索引(请注意，线段树中的索引从1开始，以简化问题)
// start 和 end 是由当前段根覆盖的子数组的索引。
int query(int node, int start, int end, int l, int r)
{
    // 完全在段外，返回1不会影响LCM
    if (end<l || start>r)
        return 1;
  
    // 完全在段内
    if (l<=start && r>=end)
        return tree[node];
  
    // 部分在段内
    int mid = (start+end)/2;
    int left_lcm = query(2*node, start, mid, l, r);
    int right_lcm = query(2*node+1, mid+1, end, l, r);
    return lcm(left_lcm, right_lcm);
}
  
// 主函数来检查上述程序
int main()
{
    // 初始化数组
    arr[0] = 5;
    arr[1] = 7;
    arr[2] = 5;
    arr[3] = 2;
    arr[4] = 10;
    arr[5] = 12;
    arr[6] = 11;
    arr[7] = 17;
    arr[8] = 14;
    arr[9] = 1;
    arr[10] = 44;
  
    // 构建线段树
    build(1, 0, 10);
  
    // 现在我们可以高效地回答每个查询
  
    // 打印 (2, 5) 的LCM
    cout << query(1, 0, 10, 2, 5) << endl;
  
    // 打印 (5, 10) 的LCM
    cout << query(1, 0, 10, 5, 10) << endl;
  
    // 打印 (0, 10) 的LCM
    cout << query(1, 0, 10, 0, 10) << endl;
  
    return 0;
}

输出结果: