Python 3程序用于范围LCM查询

在数据结构中，对查询进行范围是一种常见的数据库当前兴趣操作，用于恢复所有输出值位于上下边界之间的记录。该过程使用一些输入数据，以便将它们以高效的方式结构化在特定输入的任何子集上。范围函数，表示为range()，用于在系列上迭代for循环。在进程开始时，我们需要将开始声明为0。如果我们不小心错过了这一步，进程将一直运行并迭代循环直到结束（-1）。

范围是可以存储在变量中的最小和最大值。它们通过运算符生成，并用于调用变量的数组。它们返回一个输出列表，该列表在x至y-1之间。

示例

假设我们有一个整数数组集，并且我们需要以LCM(a,r)的形式评估查询。因此，我们必须以高效的方式评估查询。

LCM(a,r)表示在索引a和r之间存在的数组的最小公倍数。这里的两个指标都是包含在内的。

根据数学上我们都知道；L.C.M. = L.C.M Of Numerator / H.C.F of Denominator。

因此，通过使用这个逻辑，我们可以按照下面写的范围LCM查询规则进行操作：

LCM(a, r) = LCM(arr[a],  arr[a+1] , ......... ,arr[r-1], arr[r])

应用该逻辑：

输入 –

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(1, 0, 10);
cout << query(1, 0, 10, 2, 5) << endl;
cout << query(1, 0, 10, 5, 10) << endl;
cout << query(1, 0, 10, 0, 10) << endl;

输出 –

60
15708
78540

该特定过程的时间复杂度表示为O(Log N * Log n)。这里N是数组中存在的元素总数。我们需要将Log n声明为特定编码环境中LCM操作的时间要求查找器，而O(N)的时间则需要构建树以从编写的程序中获得输出。它还指示了该过程的空间要求。

范围LCM查询的算法

步骤1 – 开始
步骤2 – 为两个数字初始化变量
步骤3 – 找到每个数字的存储值
步骤4 – 用’max’函数分离变量
步骤5 – 如果最大值被第一个数字和第二个数字整除
步骤6 – 打印最大值作为LCM
步骤7 – 否则，如果不可被整除，则将其增加1
步骤8 – 然后再次执行第五步，直到打印出一个数字
步骤9 – 重复该过程，直到找到满足条件的最大值
步骤10 – 终止

范围LCM查询的语法

int find_therangelcm(int a, int tl, int ts, int r) {
    if (r > t[a])
        return -1;
    if (tl == ts)
        return tl;
    int tm = (tl + ts) / 2;
    if (t[a*2] >= r)
        return find_therangelcm(a*2, tl, tm, r);
    else 
       return find_therangelcm(a*2+1, tm+1, ts, r - t[a*2]);
}

在这个语法中，我们解释了如何在特定的编码环境中对LCM查询进行范围划分。

遵循的方法：

方法1 – 使用线段树的朴素方法。
方法2 – 以一般方式找到两个数的LCM。

使用线段树的原生方法

对于这个问题，没有更新操作，但仅仅使用朴素方法是不够的。我们需要实现一个线段树来获得可能的结果。这里我们将使用以下逻辑 –

LCM(a, b) = (a*b) / GCD(a,b)

下面是实现步骤 –

为数组建立线段树。
遍历线段树的特定范围。
计算该范围内的LCM。
打印该范围的答案。

示例1

MAX = 1000
tree = [0] * (4 * MAX)
arr = [0] * MAX
def gcd(a: int, b: int):
    if a == 0:
        return b
    return gcd(b % a, a)
def lcm(a: int, b: int):
    return (a * b) // gcd(a, b)
def build(node: int, start: int, end: int):
    if start == end:
        tree[node] = arr[start]
        return

    mid = (start + end) // 2
    build(2 * node, start, mid)
    build(2 * node + 1, mid + 1, end)
    left_lcm = tree[2 * node]
    right_lcm = tree[2 * node + 1]

    tree[node] = lcm(left_lcm, right_lcm)
def query(node: int, start: int,
        end: int, l: int, r: int):
    if end < l or start > r:
        return 1
    if l <= start and r >= end:
        return tree[node]
    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)
if __name__ == "__main__":

    # initialize the array
    arr[0] = 16
    arr[1] = 7
    arr[2] = 10
    arr[3] = 2
    arr[4] = 22
    arr[5] = 31
    arr[6] = 11
    arr[7] = 17
    arr[8] = 14
    arr[9] = 1
    arr[10] = 44
    build(1, 0, 10)
    print(query(1, 0, 10, 7, 5))
    print(query(1, 0, 10, 5, 10))
    print(query(1, 0, 10, 0, 10))

输出

1
162316
3246320

一般情况下求两个数的最小公倍数

在这个程序中，我们有两个整数n1和n2。较大的那个数被存储在max中。

示例2

def compute_lcm(x, y):
   if x > y:
       greater = x
   else:
       greater = y

   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1

   return lcm

num1 = 16
num2 = 7

print("The L.C.M. is of the given number", compute_lcm(num1, num2))