LCM сурамдары


Кыйынчылык деңгээли катуу
Көп суралган Amazon Directi Гугл Чындыгында PayPal Snapdeal Uber
согуштук тизме Query Problem Segment-Tree дарак

Маселени билдирүү

"Range LCM Queries" көйгөйүндө сизде ан бүтүн согуштук тизме жана 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) үчүн LCM 6,9,10 жана 8 360 болуп саналат

Эми дагы бир суроо үчүн, башкача айтканда, (3,7), LCM 9,10,8,7 жана 5 2520 болуп саналат

жана акырында (5,8) 8,7,5 жана 14түн LCM 280 болуп калат

LCM сурамдары

 

Algorithm

  1. Экөөнү жарыялаңыз Arrays.
  2. Куруу сегмент дарагы сол бала жана оң бала үчүн функцияларды рекурсивдүү чакыруу менен.
  3. Сол жактагы бала түйүнү жана оң бала түйүнү үчүн LCM алыңыз.
  4. Сандын LCM-н алуу үчүн, сол жана оң балдардын продуктуларын алардын GCDлерине бөлүңүз.
  5. Ар бир суроо үчүн сол жана оң жагында, диапазондун жарактуу эместигин текшериңиз, андан кийин 1, андан кийин сол түйүндүн баштапкы маанисинен азыраак, ал эми оң аяктоочу түйүндүн маанисинен чоң экендигин текшерип, андан кийин дарактын учурдагы мааниси түйүнү.
  6. Эгерде жогорудагы шарттардын бири туура эмес болсо, анда рекурсивдүү түрдө сол түйүн lcm жана оң lcm түйүнүн алуу үчүн функцияны чакырыңыз, андан кийин lcm функциясын чакырып, ушул сандардын LCMсин алыңыз.

түшүндүрүү

Бүтүн массив жана сол жана оң диапазондогу айрым суроолор берилген. Билип алыңыз LCM диапазондогу бардык сандардын бардыгы. Lcm формуласын LCM arr катарында [сол, сол + 1, ……., Оң-1, оң] колдонуп көргүлө, бирок биз бакты колдонобуз. Биз сегмент дарагын курганы жатабыз. Массивде бир гана маани бар-жогун текшерип, дарактын түйүнүнө ошол өзгөчө маанини киргизиңиз. Башкасы, биз сол баланын түйүнү үчүн массивди экиге бөлүп, бакты кура баштайбыз. Андан кийин маанилерди сол түйүн үчүн 2 * түйүн, ал эми оң жактагы түйүн үчүн, 2 * түйүн + 1 деп өткөрүп, getLCM функциясына өткөрүп, LCM маанисин алыңыз. Жана ушул эки баланын түйүндөрүнүн LCM-дерин алыңыз жана дарактын түйүн абалындагы кайтарым маанисин сактаңыз.

LCM функциясында биз сол жана оң түйүн маанилеринин эң чоң жалпы бөлүштүргүчүн табабыз. Андан кийин биз сол жана оң түйүндөрдүн көбөйтүмүнүн бөлүнүшүнүн натыйжасын жана сол жана оң түйүндүн эң чоң жалпы бөлгүчүн кайтарып беребиз.

Ар бир суроо үчүн биз сол жана оң позиция боюнча алабыз, эгерде акыркы мааниси солдон кичине же баштапкы мааниси оңдон чоң болсо, анда диапазондун аныктыгын дагы бир жолу текшерип, андан соң 1 дегенди кайтарабыз, бул жараксыз суроо. Башка учурда, эгер биз солго жана оңго баштоо менен аяктоого барабар болсо, андан чоң болсо, анда жарактуу экендигин текшерип, дарактын түйүнүндөгү маанисин кайтарабыз. Баланын сол маанисин жана оң наркын алыңыз жана ушул эки маанинин LCMин алыңыз жана ушул маанини кайтарыңыз.

коду

Range LCM Queries үчүн 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

Range LCM Queries үчүн 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" массивдеги элементтердин саны. Башка log n LCM табуу үчүн талап кылынган убакытты билдирет. Бул убакыттын татаалдыгы ар бир суроо үчүн. Жалпы убакыттын татаалдыгы O (N + Q * Log N * log n), анткени даракты куруп, андан кийин суроолорго жооп берүү үчүн O (N) убакыт талап кылынат.

Космостун татаалдыгы

 O (N) кайда "N" массивдеги элементтердин саны. Бул орун сегмент дарагын сактоо үчүн талап кылынат.