// LCM of given range queries using Segment Tree #include    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; } 

// LCM of given range queries // using Segment Tree class GFG {  static final int MAX = 1000;  // allocate space for tree  static int tree[] = new int[4 * MAX];  // declaring the array globally  static int arr[] = new int[MAX];  // Function to return gcd of a and b  static int gcd(int a int b)  {  if (a == 0) {  return b;  }  return gcd(b % a a);  }  // utility function to find lcm  static 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  static 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.  static 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 code  public static void main(String[] args)  {  // 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)  System.out.println(query(1 0 10 2 5));  // Print LCM of (5 10)  System.out.println(query(1 0 10 5 10));  // Print LCM of (0 10)  System.out.println(query(1 0 10 0 10));  } } // This code is contributed by 29AjayKumar 

# LCM of given range queries using Segment Tree MAX = 1000 # allocate space for tree tree = [0] * (4 * MAX) # declaring the array globally arr = [0] * MAX # Function to return gcd of a and b def gcd(a: int b: int): if a == 0: return b return gcd(b % a a) # utility function to find lcm def lcm(a: int b: int): 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 def build(node: int start: int end: int): # If there is only one element # in current subarray if start == end: tree[node] = arr[start] return mid = (start + end) // 2 # build left and right segments build(2 * node start mid) build(2 * node + 1 mid + 1 end) # build the parent left_lcm = tree[2 * node] 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. def query(node: int start: int end: int l: int r: int): # Completely outside the segment # returning 1 will not affect the lcm; if end < l or start > r: return 1 # completely inside the segment if l <= start and r >= end: return tree[node] # partially inside mid = (start + end) // 2 left_lcm = query(2 * node start mid l r) right_lcm = query(2 * node + 1 mid + 1 end l r) return lcm(left_lcm right_lcm) # Driver Code if __name__ == '__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) print(query(1 0 10 2 5)) # Print LCM of (5 10) print(query(1 0 10 5 10)) # Print LCM of (0 10) print(query(1 0 10 0 10)) # This code is contributed by # sanjeev2552 

// LCM of given range queries // using Segment Tree using System; using System.Collections.Generic; class GFG {  static readonly int MAX = 1000;  // allocate space for tree  static int[] tree = new int[4 * MAX];  // declaring the array globally  static int[] arr = new int[MAX];  // Function to return gcd of a and b  static int gcd(int a int b)  {  if (a == 0) {  return b;  }  return gcd(b % a a);  }  // utility function to find lcm  static 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  static 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.  static 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 code  public static void Main(String[] args)  {  // 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)  Console.WriteLine(query(1 0 10 2 5));  // Print LCM of (5 10)  Console.WriteLine(query(1 0 10 5 10));  // Print LCM of (0 10)  Console.WriteLine(query(1 0 10 0 10));  } } // This code is contributed by Rajput-Ji 

<script> // LCM of given range queries using Segment Tree const MAX = 1000 // allocate space for tree var tree = new Array(4*MAX); // declaring the array globally var arr = new Array(MAX); // Function to return gcd of a and b function gcd(a b) {  if (a == 0)  return b;  return gcd(b%a a); } //utility function to find lcm function lcm(a b) {  return Math.floor(a*b/gcd(ab)); } // Function to build the segment tree // Node starts beginning index of current subtree. // start and end are indexes in arr[] which is global function build(node start end) {  // If there is only one element in current subarray  if (start==end)  {  tree[node] = arr[start];  return;  }  let mid = Math.floor((start+end)/2);  // build left and right segments  build(2*node start mid);  build(2*node+1 mid+1 end);  // build the parent  let left_lcm = tree[2*node];  let 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. function query(node start end l 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  let mid = Math.floor((start+end)/2);  let left_lcm = query(2*node start mid l r);  let right_lcm = query(2*node+1 mid+1 end l r);  return lcm(left_lcm right_lcm); } //driver function to check the above program  //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)  document.write(query(1 0 10 2 5) +'  
');  // Print LCM of (5 10)  document.write(query(1 0 10 5 10) + '  
');  // Print LCM of (0 10)  document.write(query(1 0 10 0 10) + '  
'); // This code is contributed by Manoj. </script> 

/*package whatever //do not write package name here */ import java.util.ArrayList; import java.util.List; public class GFG {  public static int gcd(int a int b) {  if (b == 0)  return a;  return gcd(b a % b);  }  public static int lcm(int a int b) {  return a * b / gcd(a b);  }  public static List<Integer> rangeLcmQueries(List<Integer> arr List<int[]> queries) {  List<Integer> results = new ArrayList<>();  for (int[] query : queries) {  int l = query[0];  int r = query[1];  int lcmVal = arr.get(l);  for (int i = l + 1; i <= r; i++) {  lcmVal = lcm(lcmVal arr.get(i));  }  results.add(lcmVal);  }  return results;  }  public static void main(String[] args) {  List<Integer> arr = List.of(5 7 5 2 10 12 11 17 14 1 44);  List<int[]> queries = List.of(new int[]{2 5} new int[]{5 10} new int[]{0 10});  List<Integer> results = rangeLcmQueries(arr queries);  for (int result : results) {  System.out.print(result + ' ');  }  System.out.println();  } } 

from math import gcd def lcm(a b): return a*b // gcd(a b) def range_lcm_queries(arr queries): results = [] for query in queries: l r = query lcm_val = arr[l] for i in range(l+1 r+1): lcm_val = lcm(lcm_val arr[i]) results.append(lcm_val) return results # example usage arr = [5 7 5 2 10 12 11 17 14 1 44] queries = [(2 5) (5 10) (0 10)] print(range_lcm_queries(arr queries)) # output: [60 15708 78540] 

using System; using System.Collections.Generic; class GFG {  // Function to calculate the greatest common divisor (GCD)   // using Euclidean algorithm  static int GCD(int a int b)  {  if (b == 0)  return a;  return GCD(b a % b);  }  // Function to calculate the least common multiple (LCM)   // using GCD  static int LCM(int a int b)  {  return a * b / GCD(a b);  }  static List<int> RangeLcmQueries(List<int> arr List<Tuple<int int>> queries)  {  List<int> results = new List<int>();  foreach (var query in queries)  {  int l = query.Item1;  int r = query.Item2;  int lcmVal = arr[l];  for (int i = l + 1; i <= r; i++)  {  lcmVal = LCM(lcmVal arr[i]);  }  results.Add(lcmVal);  }  return results;  }  static void Main()  {  List<int> arr = new List<int> { 5 7 5 2 10 12 11 17 14 1 44 };  List<Tuple<int int>> queries = new List<Tuple<int int>> {  Tuple.Create(2 5)  Tuple.Create(5 10)  Tuple.Create(0 10)  };  List<int> results = RangeLcmQueries(arr queries);  foreach (var result in results)  {  Console.Write(result + ' ');  }  Console.WriteLine();  } } 

// JavaScript Program for the above approach // function to find out gcd function gcd(a b) {  if (b === 0) {  return a;  }  return gcd(b a % b); } // function to find out lcm function lcm(a b) {  return (a * b) / gcd(a b); } function rangeLcmQueries(arr queries) {  const results = [];  for (const query of queries) {  const l = query[0];  const r = query[1];  let lcmVal = arr[l];  for (let i = l + 1; i <= r; i++) {  lcmVal = lcm(lcmVal arr[i]);  }  results.push(lcmVal);  }  return results; } // Driver code to test above function const arr = [5 7 5 2 10 12 11 17 14 1 44]; const queries = [[2 5] [5 10] [0 10]]; const results = rangeLcmQueries(arr queries); for (const result of results) {  console.log(result + ' '); } console.log(); // THIS CODE IS CONTRIBUTED BY PIYUSH AGARWAL