范围LCM查询


难度级别
经常问 亚马逊 指令 谷歌 的确 贝宝 Snapdeal 尤伯杯
排列 查询问题 段树

问题陈述

问题“范围LCM查询”表明您有一个 整数 排列q 查询数。 每个查询都包含(左,右)作为范围。 给定的任务是找出LCM(左,右),即,包括左和右范围在内的所有数字的LCM。

使用案列

arr[] = {2, 4, 6, 9, 10, 8, 7, 5, 14, 1};
Query: {(2, 5), (3, 7), (5, 8)}
360 2520 280

说明

对于(2,5)6,9,10和8的LCM为360

现在再次用于下一个查询,即(3,7),9,10,8,7、5、2520、XNUMX和XNUMX的LCM为XNUMX

最后,对于(5,8),8,7,5和14的LCM将为280

范围LCM查询

 

算法

  1. 声明两个 数组.
  2. 建立一个 段树 通过递归调用左孩子和右孩子的函数。
  3. 获取左子节点和右子节点的LCM。
  4. 要获取数字的LCM,请用左孩子和右孩子的乘积除以他们的GCD。
  5. 对于左右两个查询,检查范围是否无效,然后返回1,否则检查左边是否小于节点的起始值,右边是否大于结束节点的值,然后返回树的当前值节点。
  6. 如果以上任何条件都不成立,则递归调用该函数以获取左节点lcm和右节点lcm,然后调用lcm函数以获取这些数字的LCM。

说明

给定一个整数数组和一些具有左右范围的查询。 找出 LCM 范围内的所有数字(包括端值在内)。 为了找出lcm,将公式实现为arr [left,left + 1,……。,right-1,right]的LCM,但是在这里,我们将使用一棵树。 我们将要构建一个段树。 我们将检查数组中是否只有一个值,然后将该特定值插入树的节点中。 否则,我们将数组拆分为一半,并开始为左子节点构建树。 然后,将值作为左节点的2 *节点传递,对于右子节点的2 *节点+1传递,并将这些值的LCM传递到getLCM函数中。 并获得这两个子节点的LCM,并将返回的值存储在树的节点位置。

在LCM函数中,我们将找到该左右节点值的最大公约数。 然后,我们将返回左节点和右节点的乘积与左节点和右节点的最大公约数的除法乘积。

对于每个查询,我们将获得左右位置,如果结束值小于左边或起始值大于右边,我们将再次检查范围的有效性,然后返回1,这是一个无效问题。 否则,如果left和right分别小于和大于等于start和end,我们将检查有效性,然后在该节点处返回树的值。 获取左子值和右子值,并获得这两个值的LCM并返回此值。

代码

范围LCM查询的C ++代码

#include<iostream>

using namespace std;

#define MAX 1000

int tree[4*MAX];

int arr[MAX];

int GCD(int a, int b)
{
    if (a == 0)
        return b;
    return GCD(b%a, a);
}
int getLCM(int a, int b)
{
    return a*b/GCD(a,b);
}
int solveQuery(int node, int start, int end, int left, int right)
{
    if (end < left || start > right)
        return 1;

    if (left<=start && right >=end)
        return tree[node];

    int mid = (start+end)/2;
    int leftChildgetLCM = solveQuery(2*node, start, mid, left, right);
    int rightChildgetLCM = solveQuery(2*node+1, mid+1, end, left, right);
    return getLCM(leftChildgetLCM, rightChildgetLCM);
}
void buildTree(int node, int start, int end)
{
    if (start==end)
    {
        tree[node] = arr[start];
        return;
    }

    int mid = (start+end)/2;
    buildTree(2*node, start, mid);
    buildTree(2*node+1, mid+1, end);

    int leftChildgetLCM = tree[2*node];
    int rightChildgetLCM = tree[2*node+1];

    tree[node] = getLCM(leftChildgetLCM, rightChildgetLCM);
}

int main()
{
    arr[0] = 2;
    arr[1] = 4;
    arr[2] = 6;
    arr[3] = 9;
    arr[4] = 10;
    arr[5] = 8;
    arr[6] = 7;
    arr[7] = 5;
    arr[8] = 14;
    arr[9] = 1;
    buildTree(1, 0, 9);
    cout << solveQuery(1, 0, 9, 2, 5) << endl;

    cout << solveQuery(1, 0, 9, 3, 7) << endl;

    cout << solveQuery(1, 0, 9, 5, 8) << endl;

    return 0;
}
360
2520
280

范围LCM查询的Java代码

class LCMQueries
{

    private static final int MAX = 1000;

    private static int tree[] = new int[4 * MAX];

    private static int arr[] = new int[MAX];

    static int GCD(int a, int b)
    {
        if (a == 0)
        {
            return b;
        }
        return GCD(b % a, a);
    }
    static int getLCM(int a, int b)
    {
        return a * b / GCD(a, b);
    }
    static void buildTree(int node, int start, int end)
    {
        if (start == end)
        {
            tree[node] = arr[start];
            return;
        }

        int mid = (start + end) / 2;
        buildTree(2 * node, start, mid);
        buildTree(2 * node + 1, mid + 1, end);
        int leftChildLCM = tree[2 * node];
        int rightChildLCM = tree[2 * node + 1];

        tree[node] = getLCM(leftChildLCM, rightChildLCM);
    }
    static int solveQuery(int node, int start,
                          int end, int left, int right)
    {
        if (end < left || start > right)
        {
            return 1;
        }

        if (left <= start && right >= end)
        {
            return tree[node];
        }

        int mid = (start + end) / 2;
        int leftChildLCM = solveQuery(2 * node, start, mid, left, right);
        int rightChildLCM = solveQuery(2 * node + 1, mid + 1, end, left, right);
        return getLCM(leftChildLCM, rightChildLCM);
    }
    public static void main(String[] args)
    {
        arr[0] = 2;
        arr[1] = 4;
        arr[2] = 6;
        arr[3] = 9;
        arr[4] = 10;
        arr[5] = 8;
        arr[6] = 7;
        arr[7] = 5;
        arr[8] = 14;
        arr[9] = 1;

        buildTree(1, 0, 9);

        System.out.println(solveQuery(1, 0, 9, 2, 5));

        System.out.println(solveQuery(1, 0, 9, 3, 7));

        System.out.println(solveQuery(1, 0, 9, 5, 8));

    }
}
360
2520
280

复杂度分析

时间复杂度

 O(Log N * Log n) 哪里 “N” 是数组中元素的数量。 另一个 登录n 表示查找LCM所需的时间。 此时间复杂度适用于每个查询。 总时间复杂度为 O(N + Q * Log N * log n), 这是因为构建树然后回答查询需要O(N)时间。

空间复杂度

 上) 哪里 “N” 是数组中元素的数量。 该空间是存储段树所必需的。