범위 LCM 쿼리

난이도 하드
자주 묻는 질문 아마존 지시 구글 과연 페이팔 스냅 딜 동네 짱
배열 쿼리 문제 세그먼트 트리 나무조회수 29

문제 정책

"범위 LCM 쿼리"문제는 정수 정렬q 쿼리 수. 각 쿼리에는 (왼쪽, 오른쪽)이 범위로 포함됩니다. 주어진 작업은 LCM (left, right), 즉 왼쪽과 오른쪽 범위에 포함 된 모든 숫자의 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의 LCM은 2520입니다.

마지막으로 (5,8) LCM 8,7,5 및 14의 경우 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을 반환합니다. 이는 잘못된 질문입니다. 그렇지 않으면 왼쪽과 오른쪽이 각각 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 (로그 N * 로그 n) 어디에 "엔" 배열의 요소 수입니다. 다른 lg n LCM을 찾는 데 필요한 시간을 나타냅니다. 이 시간 복잡성은 각 쿼리에 대한 것입니다. 총 시간 복잡성은 O (N + Q * Log N * log n), 이는 트리를 구축 한 다음 쿼리에 응답하는 데 O (N) 시간이 필요하기 때문입니다.

공간 복잡성

 의 위에) 어디에 "엔" 배열의 요소 수입니다. 이 공간은 세그먼트 트리를 저장하는 데 필요합니다.

Translate »