# 范圍 LCM 查詢 > 原文： [https://www.geeksforgeeks.org/range-lcm-queries/](https://www.geeksforgeeks.org/range-lcm-queries/) 給定一個整數數組，請評估形式為`LCM(l, r)`的查詢。 可能有很多查詢，因此可以有效地評估查詢。 ``` LCM (l, r) denotes the LCM of array elements that lie between the index l and r (inclusive of both indices) Mathematically, LCM(l, r) = LCM(arr[l], arr[l+1] , ......... , arr[r-1], arr[r]) ``` **示例**： ``` Inputs : Array = {5, 7, 5, 2, 10, 12 ,11, 17, 14, 1, 44} Queries: LCM(2, 5), LCM(5, 10), LCM(0, 10) Outputs: 60 15708 78540 Explanation : In the first query LCM(5, 2, 10, 12) = 60, similarly in other queries. ``` 一個簡單的解決方案是遍歷每個查詢的數組，并使用`LCM(a, b) = (a * b) / GCD(a, b)`計算答案 但是，由于查詢的數量可能很大，因此這種解決方案是不切實際的。 一種有效的解決方案是使用[段樹](https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/)。 回想一下，在這種情況下，不需要更新，我們可以構建一次樹，然后可以重復使用它來回答查詢。 樹中的每個節點都應存儲該特定段的 LCM 值，我們可以使用與上述相同的公式來組合這些段。 因此，我們可以有效地回答每個查詢！ 下面是相同的解決方案。 ## C++ ```cpp // LCM of given range queries using Segment Tree #include <bits/stdc++.h> using namespace std; #define MAX 1000 // allocate space for tree int tree[4*MAX]; // declaring the array globally int arr[MAX]; // Function to return gcd of a and b int gcd(int a, int b) { ????if (a == 0) ????????return b; ????return gcd(b%a, a); } //utility function to find lcm int lcm(int a, int b) { ????return a*b/gcd(a,b); } // Function to build the segment tree // Node starts beginning index of current subtree. // start and end are indexes in arr[] which is global void build(int node, int start, int end) { ????// If there is only one element in current subarray ????if (start==end) ????{ ????????tree[node] = arr[start]; ????????return; ????} ????int mid = (start+end)/2; ????// build left and right segments ????build(2*node, start, mid); ????build(2*node+1, mid+1, end); ????// build the parent ????int left_lcm = tree[2*node]; ????int right_lcm = tree[2*node+1]; ????tree[node] = lcm(left_lcm, right_lcm); } // Function to make queries for array range )l, r). // Node is index of root of current segment in segment // tree (Note that indexes in segment tree begin with 1 // for simplicity). // start and end are indexes of subarray covered by root // of current segment. int query(int node, int start, int end, int l, int r) { ????// Completely outside the segment, returning ????// 1 will not affect the lcm; ????if (end<l || start>r) ????????return 1; ????// completely inside the segment ????if (l<=start && r>=end) ????????return tree[node]; ????// partially inside ????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); } //driver function to check the above program int main() { ????//initialize the array ????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 the segment tree ????build(1, 0, 10); ????// Now we can answer each query efficiently ????// Print LCM of (2, 5) ????cout << query(1, 0, 10, 2, 5) << endl; ????// Print LCM of (5, 10) ????cout << query(1, 0, 10, 5, 10) << endl; ????// Print LCM of (0, 10) ????cout << query(1, 0, 10, 0, 10) << endl; ????return 0; } ```