// 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  (  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   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