Consultas LCM de rango

Dada una array de enteros, evalúe consultas de la forma LCM(l, r). Puede haber muchas consultas, por lo tanto, evalúe las consultas de manera eficiente. 

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])

Ejemplos: 

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.

Una solución ingenua sería recorrer la array para cada consulta y calcular la respuesta usando, 
LCM(a, b) = (a*b) / GCD(a,b)
Sin embargo, como la cantidad de consultas puede ser grande, esta solución sería poco práctico.
Una solución eficiente sería utilizar el árbol de segmentos . Recuerde que en este caso, donde no se requiere actualización, podemos construir el árbol una vez y usarlo repetidamente para responder a las consultas. Cada Node en el árbol debe almacenar el valor de LCM para ese segmento en particular y podemos usar la misma fórmula anterior para combinar los segmentos. ¡Por lo tanto, podemos responder cada consulta de manera eficiente!

A continuación se muestra una solución para el mismo. 

// 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;
}

// 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) +"<br>");
  
    // Print LCM of (5, 10)
    document.write(query(1, 0, 10, 5, 10) + "<br>");
  
    // Print LCM of (0, 10)
    document.write(query(1, 0, 10, 0, 10) + "<br>");
  
// This code is contributed by Manoj.
</script>

60
15708
78540

Tema relacionado: Árbol de segmentos

Este artículo es una contribución de Ashutosh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.