Calcule la suma de GCD sobre todos los subarreglos

Dada una array de enteros, la tarea es calcular la suma de GCD de todos los subarreglos de una array. El GCD de una array se define como el GCD de todos los elementos presentes en él. Más formalmente, $GCD(A[n]) = GCD(A_1, A_2, A_3....A_n)$ . La suma de todos los GCD se puede definir como $\sum_{i=1}^{n}\sum_{j=i}^{n} GCD(A_{ij})$ donde $A_{ij}$ denota el subarreglo que comienza en el índice i-ésimo y termina en el índice j-ésimo.
Ejemplos:

Entrada 1: N = 5, A = {1,2,3,4,5}
Salida 1: 25
Explicación:
Los subarreglos de longitud uno son [1], [2], [3], [4], [5 ] y la suma de sus GCD es 15, de manera similar, los subarreglos de longitud 2 son [1, 2], [2, 3], [3, 4], [4, 5], y la suma de sus GCD es 4, de manera similar para la longitud 3, la suma es 3, de manera similar para la longitud 4, la suma es 2, de manera similar para la longitud 5, la suma es 1.
La suma total se convierte en 25.
Entrada 2: N = 6, A = {2,2, 2,3,5,5}
Salida 2: 41

Requisitos previos Enfoque de árbol de segmento de
búsqueda binaria para calcular GCD en un rango de índice Tabla dispersa para calcular GCD en un rango de índice

Enfoque ingenuo (complejidad O (n ^ 3))
Podemos encontrar cada subarreglo en complejidad O (n ^ 2) y podemos atravesarlo para encontrar el GCD de ese subarreglo y agregarlo a la respuesta total.
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find
// Sum of GCD over all subarrays.
  
#include <bits/stdc++.h>
using namespace std;
  
// Utility function to calculate
// sum of gcd of all sub-arrays.
  
int findGCDSum(int n, int a[])
{
    int GCDSum = 0;
    int tempGCD = 0;
    for (int i = 0; i < n; i++) {
        // Fixing the starting index of a subarray
        for (int j = i; j < n; j++) {
            // Fixing the ending index of a subarray
            tempGCD = 0;
            for (int k = i; k <= j; k++) {
                // Finding the GCD of this subarray
                tempGCD = __gcd(tempGCD, a[k]);
            }
            // Adding this GCD in our sum
            GCDSum += tempGCD;
        }
    }
    return GCDSum;
}
  
// Driver Code
int main()
{
    int n = 5;
    int a[] = { 1, 2, 3, 4, 5 };
    int totalSum = findGCDSum(n, a);
    cout << totalSum << "\n";
}

Java

// Java program to find
// Sum of GCD over all subarrays.
class GFG
{
  
// Utility function to calculate
// sum of gcd of all sub-arrays.
static int findGCDSum(int n, int a[])
{
    int GCDSum = 0;
    int tempGCD = 0;
    for (int i = 0; i < n; i++)
    {
        // Fixing the starting index of a subarray
        for (int j = i; j < n; j++)
        {
            // Fixing the ending index of a subarray
            tempGCD = 0;
            for (int k = i; k <= j; k++) 
            {
                // Finding the GCD of this subarray
                tempGCD = __gcd(tempGCD, a[k]);
            }
              
            // Adding this GCD in our sum
            GCDSum += tempGCD;
        }
    }
    return GCDSum;
}
  
static int __gcd(int a, int b) 
{ 
    return b == 0 ? a : __gcd(b, a % b);     
} 
  
// Driver Code
public static void main(String[] args)
{
    int n = 5;
    int a[] = { 1, 2, 3, 4, 5 };
    int totalSum = findGCDSum(n, a);
    System.out.print(totalSum + "\n");
}
}
  
// This code is contributed by 29AjayKumar

Python3

# Python3 program to find
# Sum of GCD over all subarrays.
  
# Utility function to calculate
# sum of gcd of all sub-arrays.
def findGCDSum(n, a):
    GCDSum = 0;
    tempGCD = 0;
    for i in range(n):
          
        # Fixing the starting index of a subarray
        for j in range(i, n):
              
            # Fixing the ending index of a subarray
            tempGCD = 0;
            for k in range(i, j + 1):
                  
                # Finding the GCD of this subarray
                tempGCD = __gcd(tempGCD, a[k]);
                  
            # Adding this GCD in our sum
            GCDSum += tempGCD;
  
    return GCDSum;
  
def __gcd(a, b):
    return a if(b == 0 ) else __gcd(b, a % b);     
  
# Driver Code
if __name__ == '__main__':
    n = 5;
    a = [1, 2, 3, 4, 5];
    totalSum = findGCDSum(n, a);
    print(totalSum);
  
# This code is contributed by PrinciRaj1992

C#

// C# program to find
// Sum of GCD over all subarrays.
using System;
  
class GFG
{
  
// Utility function to calculate
// sum of gcd of all sub-arrays.
static int findGCDSum(int n, int []a)
{
    int GCDSum = 0;
    int tempGCD = 0;
    for (int i = 0; i < n; i++)
    {
        // Fixing the starting index of a subarray
        for (int j = i; j < n; j++)
        {
            // Fixing the ending index of a subarray
            tempGCD = 0;
            for (int k = i; k <= j; k++) 
            {
                // Finding the GCD of this subarray
                tempGCD = __gcd(tempGCD, a[k]);
            }
              
            // Adding this GCD in our sum
            GCDSum += tempGCD;
        }
    }
    return GCDSum;
}
  
static int __gcd(int a, int b) 
{ 
    return b == 0 ? a : __gcd(b, a % b);     
} 
  
// Driver Code
public static void Main(String[] args)
{
    int n = 5;
    int []a = { 1, 2, 3, 4, 5 };
    int totalSum = findGCDSum(n, a);
    Console.Write(totalSum + "\n");
}
}
  
// This code is contributed by Rajput-Ji

Javascript

<script>
// javascript program to find
// Sum of GCD over all subarrays.    
  
// Utility function to calculate
    // sum of gcd of all sub-arrays.
    function findGCDSum(n , a) 
    {
        var GCDSum = 0;
        var tempGCD = 0;
        for (i = 0; i < n; i++)
        {
          
            // Fixing the starting index of a subarray
            for (j = i; j < n; j++)
            {
              
                // Fixing the ending index of a subarray
                tempGCD = 0;
                for (k = i; k <= j; k++) 
                {
                  
                    // Finding the GCD of this subarray
                    tempGCD = __gcd(tempGCD, a[k]);
                }
  
                // Adding this GCD in our sum
                GCDSum += tempGCD;
            }
        }
        return GCDSum;
    }
  
    function __gcd(a , b) 
    {
        return b == 0 ? a : __gcd(b, a % b);
    }
  
    // Driver Code
        var n = 5;
        var a = [ 1, 2, 3, 4, 5 ];
        var totalSum = findGCDSum(n, a);
        document.write(totalSum + "<br/>");
  
// This code is contributed by umadevi9616 
</script>

Producción:

Podemos optimizar la parte donde calcula el GCD de un subarreglo. Podemos usar un árbol de segmentos o una tabla dispersa para optimizar la complejidad a O(n^2 * logn) (para árboles de segmentos) o a O(n^2) ( para tabla dispersa)
Enfoque eficiente (O(n*(logn)^2) complejidad) :
este enfoque aprovecha la observación de que al agregar un nuevo elemento a una array, el nuevo GCD de la array siempre será menor o igual al GCD anterior de la array antes de agregar el elemento.
Creamos tres punteros, llamémoslos startPointer , endPointer y prevEndPointer . Inicialmente, los tres apuntan al primer elemento de nuestra array. Inicializamos una variable tempGCDcon el valor del primer elemento. Ahora encontraremos la suma de GCD de todos los subarreglos comenzando con el primer elemento.
Ahora, según nuestra observación anterior, si movemos el EndPointer hacia la derecha una posición y calculamos el GCD de estos dos elementos que apuntan StartPointer y EndPointer, siempre será menor o igual que tempGCD. Entonces, si queremos averiguar cuántos subarreglos tienen el GCD como tempGCD, debemos encontrar una posición adecuada de endPointer, donde el subarreglo que comienza en startPointer y termina en endPointer tendrá el valor de su GCD menos que tempGCD, y el valor de endPointer debe ser lo mínimo posible, entonces la diferencia de prevEndPointer y endPointer nos dará la cantidad de subarreglos que tienen su GCD como tempGCD. Ahora, podemos agregar este valor(tempGCD*(endPointer-prevEndPointer)) , que denota la suma del GCD para este grupo particular de subarreglos, en nuestra variable finalAns que almacena la suma del GCD de todos los subarreglos.
Ahora queda la pregunta, ¿cómo encontraremos la posición adecuada de endPointer donde el GCD disminuye? Ahí es donde la búsqueda binariaentra en uso, tenemos fijo el punto inicial de nuestra array y necesitamos variar el punto final, llamémoslos L y R, así que para cualquier R. Inicializamos alto como N y bajo como prevEndPointer, y medio como (alto +low)/2, ahora si verificamos el valor de GCD[L, mid], lo comparamos con el valor de tempGCD, y si es menor, entonces R podría ser una posición adecuada para endPointer, pero podría ser el caso de que algún valor más pequeño se convierta en nuestra respuesta, por lo que cambiamos alto para que sea mid-1, y si se encuentra que GCD[L, mid] es igual a tempGCD, entonces deberíamos cambiar bajo para que sea mid+1, y el valor de mid+1 podría ser la respuesta, por lo que almacenamos el valor de mid en una variable nextPos . Por fin devolvemos el valor de nextPos+1 .
El valor de GCD[L, mid] se puede calcular de manera eficiente usando unÁrbol de segmentos en complejidad O (logN) o utilizando una tabla dispersa en complejidad O (1).
Este tipo de búsqueda binaria nos encuentra la posición adecuada de endPointer. Después de encontrar esta posición y agregar a finalAns, cambiamos prevEndPointer a endPointer y tempGCD a GCD[startPointer, endPointer] , y nuevamente comenzamos el proceso de encontrar el siguiente endPointer. Esto se detendrá una vez que el valor de endPointer se convierta en N, y luego debemos mover startPointer hacia la derecha, lo que contará la suma de GCD de todos los subarreglos que comienzan con el segundo elemento. Esto continuará hasta que el valor de startPointer se convierta en N.
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find Sum
// of GCD over all subarrays
  
#include <bits/stdc++.h>
using namespace std;
  
//int a[100001];
int SparseTable[100001][51];
  
// Build Sparse Table
void buildSparseTable(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        SparseTable[i][0] = a[i];
    }
    // Building the Sparse Table for GCD[L, R] Queries
    for (int j = 1; j <= 19; j++) {
        for (int i = 0; i <= n - (1 << j); i++) {
            SparseTable[i][j] = __gcd(SparseTable[i][j - 1], 
                    SparseTable[i + (1 << (j - 1))][j - 1]);
        }
    }
}
  
// Utility Function to calculate GCD in range [L,R]
int queryForGCD(int L, int R)
{
    int returnValue;
      
    // Calculating where the answer is 
    // stored in our Sparse Table
    int j = int(log2(R - L + 1));
      
    returnValue = __gcd(SparseTable[L][j], 
                    SparseTable[R - (1 << j) + 1][j]);
                      
    return returnValue;
}
  
// Utility Function to find next-farther 
// position where gcd is same 
int nextPosition(int tempGCD, int startPointer, 
                            int prevEndPointer, int n)
{
    int high = n - 1;
    int low = prevEndPointer;
    int mid = prevEndPointer;
    int nextPos = prevEndPointer;
      
    // BinarySearch for Next Position 
    // for EndPointer
    while (high >= low) {
          
        mid = ((high + low) >> 1);
          
        if (queryForGCD(startPointer, mid) == tempGCD) {
            nextPos = mid;
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
      
    return nextPos + 1;
}
  
// Utility function to calculate 
// sum of gcd 
int calculateSum(int a[], int n)
{
    buildSparseTable(a, n);
      
    int endPointer, startPointer, prevEndPointer, tempGCD;
      
    int tempAns = 0;
      
    for (int i = 0; i < n; i++) {
        // Initializing all the values
        endPointer = i;
        startPointer = i;
        prevEndPointer = i;
        tempGCD = a[i];
        while (endPointer < n) {
  
            // Finding the next position for endPointer
            endPointer = nextPosition(tempGCD, startPointer, 
                                            prevEndPointer, n);
  
            // Adding the suitable sum to our answer
            tempAns += ((endPointer - prevEndPointer) * tempGCD);
  
            // Changing prevEndPointer
            prevEndPointer = endPointer;
  
            if (endPointer < n) {
                // Recalculating tempGCD
                tempGCD = __gcd(tempGCD, a[endPointer]);
            }
        }
    }
    return tempAns;
}
  
// Driver Code
int main()
{
    int n = 6;
      
    int a[] = {2, 2, 2, 3, 5, 5};
      
    cout << calculateSum(a, n) << "\n";
      
    return 0;
}

Java

// Java program to find Sum
// of GCD over all subarrays
class GFG 
{
  
//int a[100001];
static int [][]SparseTable = new int[100001][51];
  
// Build Sparse Table
static void buildSparseTable(int a[], int n)
{
    for (int i = 0; i < n; i++) 
    {
        SparseTable[i][0] = a[i];
    }
      
    // Building the Sparse Table 
    // for GCD[L, R] Queries
    for (int j = 1; j <= 19; j++)
    {
        for (int i = 0; i <= n - (1 << j); i++) 
        {
            SparseTable[i][j] = __gcd(SparseTable[i][j - 1], 
                     SparseTable[i + (1 << (j - 1))][j - 1]);
        }
    }
}
  
// Utility Function to calculate GCD in range [L,R]
static int queryForGCD(int L, int R)
{
    int returnValue;
      
    // Calculating where the answer is 
    // stored in our Sparse Table
    int j = (int) (Math.log(R - L + 1));
      
    returnValue = __gcd(SparseTable[L][j], 
         SparseTable[R - (1 << j) + 1][j]);
                      
    return returnValue;
}
  
// Utility Function to find next-farther 
// position where gcd is same 
static int nextPosition(int tempGCD, int startPointer, 
                        int prevEndPointer, int n)
{
    int high = n - 1;
    int low = prevEndPointer;
    int mid = prevEndPointer;
    int nextPos = prevEndPointer;
      
    // BinarySearch for Next Position 
    // for EndPointer
    while (high >= low) 
    {
        mid = ((high + low) >> 1);
          
        if (queryForGCD(startPointer, mid) == tempGCD) 
        {
            nextPos = mid;
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return nextPos + 1;
}
  
// Utility function to calculate 
// sum of gcd 
static int calculateSum(int a[], int n)
{
    buildSparseTable(a, n);
      
    int endPointer, startPointer, 
        prevEndPointer, tempGCD;
      
    int tempAns = 0;
      
    for (int i = 0; i < n; i++)
    {
        // Initializing all the values
        endPointer = i;
        startPointer = i;
        prevEndPointer = i;
        tempGCD = a[i];
        while (endPointer < n) 
        {
  
            // Finding the next position for endPointer
            endPointer = nextPosition(tempGCD, startPointer, 
                                         prevEndPointer, n);
  
            // Adding the suitable sum to our answer
            tempAns += ((endPointer - 
                         prevEndPointer) * tempGCD);
  
            // Changing prevEndPointer
            prevEndPointer = endPointer;
  
            if (endPointer < n)
            {
                  
                // Recalculating tempGCD
                tempGCD = __gcd(tempGCD, a[endPointer]);
            }
        }
    }
    return tempAns;
}
  
static int __gcd(int a, int b) 
{ 
    return b == 0? a:__gcd(b, a % b);     
}
  
// Driver code
public static void main(String[] args) 
{
    int n = 6;
      
    int a[] = {2, 2, 2, 3, 5, 5};
      
    System.out.println(calculateSum(a, n));
}
}
  
// This code is contributed by PrinciRaj1992

Python3

# Python3 program to find Sum
# of GCD over all subarrays
from math import gcd as __gcd,log,floor
SparseTable = [ [0 for i in range(51)] for i in range(100001)]
  
# Build Sparse Table
def buildSparseTable(a, n):
    for i in range(n):
        SparseTable[i][0] = a[i]
  
    # Building the Sparse Table for GCD[L, R] Queries
    for j in range(1,20):
        for i in range(n - (1 << j)+1):
            SparseTable[i][j] = __gcd(SparseTable[i][j - 1],
                                SparseTable[i + (1 << (j - 1))][j - 1])
  
# Utility Function to calculate GCD in range [L,R]
def queryForGCD(L, R):
  
    # Calculating where the answer is
    # stored in our Sparse Table
    j = floor(log(R - L + 1, 2))
  
    returnValue = __gcd(SparseTable[L][j],
                SparseTable[R - (1 << j) + 1][j])
  
    return returnValue
  
  
# Utility Function to find next-farther
# position where gcd is same
def nextPosition(tempGCD, startPointer,prevEndPointer, n):
    high = n - 1
    low = prevEndPointer
    mid = prevEndPointer
    nextPos = prevEndPointer
  
    # BinarySearch for Next Position
    # for EndPointer
    while (high >= low):
  
        mid = ((high + low) >> 1)
  
        if (queryForGCD(startPointer, mid) == tempGCD):
            nextPos = mid
            low = mid + 1
        else:
            high = mid - 1
  
    return nextPos + 1
  
# Utility function to calculate
# sum of gcd
def calculateSum(a, n):
    buildSparseTable(a, n)
  
    tempAns = 0
  
    for i in range(n):
          
        # Initializing all the values
        endPointer = i
        startPointer = i
        prevEndPointer = i
        tempGCD = a[i]
        while (endPointer < n):
  
            # Finding the next position for endPointer
            endPointer = nextPosition(tempGCD, 
                        startPointer,prevEndPointer, n)
  
            # Adding the suitable sum to our answer
            tempAns += ((endPointer - prevEndPointer) * tempGCD)
  
            # Changing prevEndPointer
            prevEndPointer = endPointer
  
            if (endPointer < n):
                  
                # Recalculating tempGCD
                tempGCD = __gcd(tempGCD, a[endPointer])
  
    return tempAns
  
# Driver code
if __name__ == '__main__':
    n = 6
  
    a = [2, 2, 2, 3, 5, 5]
  
    print(calculateSum(a, n))
  
# This code is contributed by mohit kumar 29

C#

// C# program to find Sum
// of GCD over all subarrays
using System;
  
class GFG 
{
  
//int a[100001];
static int [,]SparseTable = new int[100001,51];
  
// Build Sparse Table
static void buildSparseTable(int []a, int n)
{
    for (int i = 0; i < n; i++) 
    {
        SparseTable[i,0] = a[i];
    }
      
    // Building the Sparse Table 
    // for GCD[L, R] Queries
    for (int j = 1; j <= 19; j++)
    {
        for (int i = 0; i <= n - (1 << j); i++) 
        {
            SparseTable[i,j] = __gcd(SparseTable[i,j - 1], 
                    SparseTable[i + (1 << (j - 1)),j - 1]);
        }
    }
}
  
// Utility Function to calculate GCD in range [L,R]
static int queryForGCD(int L, int R)
{
    int returnValue;
      
    // Calculating where the answer is 
    // stored in our Sparse Table
    int j = (int) (Math.Log(R - L + 1));
      
    returnValue = __gcd(SparseTable[L,j], 
        SparseTable[R - (1 << j) + 1,j]);
                      
    return returnValue;
}
  
// Utility Function to find next-farther 
// position where gcd is same 
static int nextPosition(int tempGCD, int startPointer, 
                        int prevEndPointer, int n)
{
    int high = n - 1;
    int low = prevEndPointer;
    int mid = prevEndPointer;
    int nextPos = prevEndPointer;
      
    // BinarySearch for Next Position 
    // for EndPointer
    while (high >= low) 
    {
        mid = ((high + low) >> 1);
          
        if (queryForGCD(startPointer, mid) == tempGCD) 
        {
            nextPos = mid;
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return nextPos + 1;
}
  
// Utility function to calculate 
// sum of gcd 
static int calculateSum(int []a, int n)
{
    buildSparseTable(a, n);
      
    int endPointer, startPointer, 
        prevEndPointer, tempGCD;
      
    int tempAns = 0;
      
    for (int i = 0; i < n; i++)
    {
        // Initializing all the values
        endPointer = i;
        startPointer = i;
        prevEndPointer = i;
        tempGCD = a[i];
        while (endPointer < n) 
        {
  
            // Finding the next position for endPointer
            endPointer = nextPosition(tempGCD, startPointer, 
                                        prevEndPointer, n);
  
            // Adding the suitable sum to our answer
            tempAns += ((endPointer - 
                        prevEndPointer) * tempGCD);
  
            // Changing prevEndPointer
            prevEndPointer = endPointer;
  
            if (endPointer < n)
            {
                  
                // Recalculating tempGCD
                tempGCD = __gcd(tempGCD, a[endPointer]);
            }
        }
    }
    return tempAns;
}
  
static int __gcd(int a, int b) 
{ 
    return b == 0? a:__gcd(b, a % b);     
}
  
// Driver code
public static void Main(String[] args) 
{
    int n = 6;
      
    int []a = {2, 2, 2, 3, 5, 5};
      
    Console.WriteLine(calculateSum(a, n));
}
}
  
// This code contributed by PrinciRaj1992

Javascript

<script>
  
// JavaScript program to find Sum
// of GCD over all subarrays
  
// int a[100001];
let SparseTable = new Array(100001);
for(let i=0;i<100001;i++)
{
    SparseTable[i]=new Array(51);
    for(let j=0;j<51;j++)
    {
        SparseTable[i][j]=0;
    }
}
  
// Build Sparse Table
function buildSparseTable(a,n)
{
    for (let i = 0; i < n; i++)
    {
        SparseTable[i][0] = a[i];
    }
       
    // Building the Sparse Table
    // for GCD[L, R] Queries
    for (let j = 1; j <= 19; j++)
    {
        for (let i = 0; i <= n - (1 << j); i++)
        {
            SparseTable[i][j] = __gcd(SparseTable[i][j - 1],
                     SparseTable[i + (1 << (j - 1))][j - 1]);
        }
    }
}
  
// Utility Function to calculate GCD in range [L,R]
function queryForGCD(L,R)
{
    let returnValue;
       
    // Calculating where the answer is
    // stored in our Sparse Table
    let j =  Math.floor(Math.log(R - L + 1));
       
    returnValue = __gcd(SparseTable[L][j],
         SparseTable[R - (1 << j) + 1][j]);
                       
    return returnValue;
}
  
// Utility Function to find next-farther
// position where gcd is same
function nextPosition(tempGCD,startPointer,prevEndPointer,n)
{
    let high = n - 1;
    let low = prevEndPointer;
    let mid = prevEndPointer;
    let nextPos = prevEndPointer;
       
    // BinarySearch for Next Position
    // for EndPointer
    while (high >= low)
    {
        mid = ((high + low) >> 1);
           
        if (queryForGCD(startPointer, mid) == tempGCD)
        {
            nextPos = mid;
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return nextPos + 1;
}
  
// Utility function to calculate
// sum of gcd
function calculateSum(a,n)
{
    buildSparseTable(a, n);
       
    let endPointer, startPointer,
        prevEndPointer, tempGCD;
       
    let tempAns = 0;
       
    for (let i = 0; i < n; i++)
    {
        // Initializing all the values
        endPointer = i;
        startPointer = i;
        prevEndPointer = i;
        tempGCD = a[i];
        while (endPointer < n)
        {
   
            // Finding the next position for endPointer
            endPointer = nextPosition(tempGCD, startPointer,
                                         prevEndPointer, n);
   
            // Adding the suitable sum to our answer
            tempAns += ((endPointer -
                         prevEndPointer) * tempGCD);
   
            // Changing prevEndPointer
            prevEndPointer = endPointer;
   
            if (endPointer < n)
            {
                   
                // Recalculating tempGCD
                tempGCD = __gcd(tempGCD, a[endPointer]);
            }
        }
    }
    return tempAns;
}
  
function __gcd(a,b)
{
    return b == 0? a: __gcd(b, a % b);
}
  
// Driver code
let n = 6;
let a=[2, 2, 2, 3, 5, 5];
document.write(calculateSum(a, n));
  
  
// This code is contributed by patel2127
  
</script>

Producción:

Complejidad de tiempo : O(N * log(max(A[i]) * log(N))
La complejidad de tiempo de la solución anterior incluye el conocimiento de saber cuántas veces se llamará a la búsqueda binaria y, por lo tanto, necesitamos saber cuántas veces puede cambiar el valor de endPointer.Este valor resulta ser aproximadamente log(A[i]) , porque, para cualquier número X, la cantidad de veces que su GCD puede disminuir al ser aporreado con otro número es el valor más alto potencia de cualquiera de sus divisores primos. Entonces, la complejidad del tiempo total se vuelve aproximadamente O (N * log (max (A [i]) * log (N)) donde otro factor logN viene debido a la búsqueda binaria. Este es el caso cuando use Sparse Table, si usamos Segment Tree para consultas GCD, aparecerá otro término de log(N).

Tema relacionado: Árbol de segmentos

Publicación traducida automáticamente

Artículo escrito por Raunaq Singh 3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta