Zakres zapytań LCM
Mając tablicę arr[] liczb całkowitych o rozmiarze N i tablicę Q zapytań query[], gdzie każde zapytanie jest typu [L R] oznaczającego zakres od indeksu L do indeksu R, zadaniem jest znalezienie LCM wszystkich liczb z zakresu dla wszystkich zapytań.
Przykłady:
Wejście: tablica [] = {5 7 5 2 10 12 11 17 14 1 44}
zapytanie[] = {{2 5} {5 10} {0 10}}
Wyjście: 6015708 78540
Wyjaśnienie: W pierwszym zapytaniu LCM(5 2 10 12) = 60
W drugim zapytaniu LCM(12 11 17 14 1 44) = 15708
W ostatnim zapytaniu LCM(5 7 5 2 10 12 11 17 14 1 44) = 78540Wejście: arr[] = {2 4 8 16} zapytanie[] = {{2 3} {0 1}}
Wyjście: 16 4
Naiwne podejście: Podejście to opiera się na następującej idei matematycznej:
Matematycznie LCM(l r) = LCM(arr[l] arr[l+1] . . arr[r-1] arr[r]) i
LCM(a b) = (a*b) / GCD(ab)
Zatem przejrzyj tablicę dla każdego zapytania i oblicz odpowiedź, korzystając z powyższego wzoru dla LCM.
Złożoność czasowa: O(N * Q)
Przestrzeń pomocnicza: O(1)
Używanie zapytań RangeLCM Drzewo segmentowe :
Ponieważ liczba zapytań może być duża, naiwne rozwiązanie byłoby niepraktyczne. Czas ten można skrócić
W przypadku tego problemu nie ma operacji aktualizacji. Możemy więc początkowo zbudować drzewo segmentów i użyć go do odpowiedzi na zapytania w czasie logarytmicznym.
Każdy węzeł drzewa powinien przechowywać wartość LCM dla tego konkretnego segmentu i możemy użyć tej samej formuły co powyżej, aby połączyć segmenty.
Aby wdrożyć pomysł, wykonaj kroki wymienione poniżej:
- Z podanej tablicy zbuduj drzewo segmentowe.
- Przejdź przez zapytania. Dla każdego zapytania:
- Znajdź ten konkretny zakres w drzewie segmentu.
- Użyj powyższego wzoru, aby połączyć segmenty i obliczyć LCM dla tego zakresu.
- Wydrukuj odpowiedź dla tego segmentu.
Poniżej implementacja powyższego podejścia.
C++ // LCM of given range queries using Segment Tree #include using namespace std ; #define MAX 1000 // allocate space for tree int tree [ 4 * MAX ]; // declaring the array globally int arr [ MAX ]; // Function to return gcd of a and b int gcd ( int a int b ) { if ( a == 0 ) return b ; return gcd ( b % a a ); } // utility function to find lcm int lcm ( int a int b ) { return a * b / gcd ( a b ); } // Function to build the segment tree // Node starts beginning index of current subtree. // start and end are indexes in arr[] which is global void build ( int node int start int end ) { // If there is only one element in current subarray if ( start == end ) { tree [ node ] = arr [ start ]; return ; } int mid = ( start + end ) / 2 ; // build left and right segments build ( 2 * node start mid ); build ( 2 * node + 1 mid + 1 end ); // build the parent int left_lcm = tree [ 2 * node ]; int right_lcm = tree [ 2 * node + 1 ]; tree [ node ] = lcm ( left_lcm right_lcm ); } // Function to make queries for array range )l r). // Node is index of root of current segment in segment // tree (Note that indexes in segment tree begin with 1 // for simplicity). // start and end are indexes of subarray covered by root // of current segment. int query ( int node int start int end int l int r ) { // Completely outside the segment returning // 1 will not affect the lcm; if ( end < l || start > r ) return 1 ; // completely inside the segment if ( l <= start && r >= end ) return tree [ node ]; // partially inside int mid = ( start + end ) / 2 ; int left_lcm = query ( 2 * node start mid l r ); int right_lcm = query ( 2 * node + 1 mid + 1 end l r ); return lcm ( left_lcm right_lcm ); } // driver function to check the above program int main () { // initialize the array 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 the segment tree build ( 1 0 10 ); // Now we can answer each query efficiently // Print LCM of (2 5) cout < < query ( 1 0 10 2 5 ) < < endl ; // Print LCM of (5 10) cout < < query ( 1 0 10 5 10 ) < < endl ; // Print LCM of (0 10) cout < < query ( 1 0 10 0 10 ) < < endl ; return 0 ; }
Java // LCM of given range queries // using Segment Tree class GFG { static final int MAX = 1000 ; // allocate space for tree static int tree [] = new int [ 4 * MAX ] ; // declaring the array globally static int arr [] = new int [ MAX ] ; // Function to return gcd of a and b static int gcd ( int a int b ) { if ( a == 0 ) { return b ; } return gcd ( b % a a ); } // utility function to find lcm static int lcm ( int a int b ) { return a * b / gcd ( a b ); } // Function to build the segment tree // Node starts beginning index // of current subtree. start and end // are indexes in arr[] which is global static void build ( int node int start int end ) { // If there is only one element // in current subarray if ( start == end ) { tree [ node ] = arr [ start ] ; return ; } int mid = ( start + end ) / 2 ; // build left and right segments build ( 2 * node start mid ); build ( 2 * node + 1 mid + 1 end ); // build the parent int left_lcm = tree [ 2 * node ] ; int right_lcm = tree [ 2 * node + 1 ] ; tree [ node ] = lcm ( left_lcm right_lcm ); } // Function to make queries for // array range )l r). Node is index // of root of current segment in segment // tree (Note that indexes in segment // tree begin with 1 for simplicity). // start and end are indexes of subarray // covered by root of current segment. static int query ( int node int start int end int l int r ) { // Completely outside the segment returning // 1 will not affect the lcm; if ( end < l || start > r ) { return 1 ; } // completely inside the segment if ( l <= start && r >= end ) { return tree [ node ] ; } // partially inside int mid = ( start + end ) / 2 ; int left_lcm = query ( 2 * node start mid l r ); int right_lcm = query ( 2 * node + 1 mid + 1 end l r ); return lcm ( left_lcm right_lcm ); } // Driver code public static void main ( String [] args ) { // initialize the array 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 the segment tree build ( 1 0 10 ); // Now we can answer each query efficiently // Print LCM of (2 5) System . out . println ( query ( 1 0 10 2 5 )); // Print LCM of (5 10) System . out . println ( query ( 1 0 10 5 10 )); // Print LCM of (0 10) System . out . println ( query ( 1 0 10 0 10 )); } } // This code is contributed by 29AjayKumar
Python # LCM of given range queries using Segment Tree MAX = 1000 # allocate space for tree tree = [ 0 ] * ( 4 * MAX ) # declaring the array globally arr = [ 0 ] * MAX # Function to return gcd of a and b def gcd ( a : int b : int ): if a == 0 : return b return gcd ( b % a a ) # utility function to find lcm def lcm ( a : int b : int ): return ( a * b ) // gcd ( a b ) # Function to build the segment tree # Node starts beginning index of current subtree. # start and end are indexes in arr[] which is global def build ( node : int start : int end : int ): # If there is only one element # in current subarray if start == end : tree [ node ] = arr [ start ] return mid = ( start + end ) // 2 # build left and right segments build ( 2 * node start mid ) build ( 2 * node + 1 mid + 1 end ) # build the parent left_lcm = tree [ 2 * node ] right_lcm = tree [ 2 * node + 1 ] tree [ node ] = lcm ( left_lcm right_lcm ) # Function to make queries for array range )l r). # Node is index of root of current segment in segment # tree (Note that indexes in segment tree begin with 1 # for simplicity). # start and end are indexes of subarray covered by root # of current segment. def query ( node : int start : int end : int l : int r : int ): # Completely outside the segment # returning 1 will not affect the lcm; if end < l or start > r : return 1 # completely inside the segment if l <= start and r >= end : return tree [ node ] # partially inside 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 ) # Driver Code if __name__ == '__main__' : # initialize the array 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 the segment tree build ( 1 0 10 ) # Now we can answer each query efficiently # Print LCM of (2 5) print ( query ( 1 0 10 2 5 )) # Print LCM of (5 10) print ( query ( 1 0 10 5 10 )) # Print LCM of (0 10) print ( query ( 1 0 10 0 10 )) # This code is contributed by # sanjeev2552
C# // LCM of given range queries // using Segment Tree using System ; using System.Collections.Generic ; class GFG { static readonly int MAX = 1000 ; // allocate space for tree static int [] tree = new int [ 4 * MAX ]; // declaring the array globally static int [] arr = new int [ MAX ]; // Function to return gcd of a and b static int gcd ( int a int b ) { if ( a == 0 ) { return b ; } return gcd ( b % a a ); } // utility function to find lcm static int lcm ( int a int b ) { return a * b / gcd ( a b ); } // Function to build the segment tree // Node starts beginning index // of current subtree. start and end // are indexes in []arr which is global static void build ( int node int start int end ) { // If there is only one element // in current subarray if ( start == end ) { tree [ node ] = arr [ start ]; return ; } int mid = ( start + end ) / 2 ; // build left and right segments build ( 2 * node start mid ); build ( 2 * node + 1 mid + 1 end ); // build the parent int left_lcm = tree [ 2 * node ]; int right_lcm = tree [ 2 * node + 1 ]; tree [ node ] = lcm ( left_lcm right_lcm ); } // Function to make queries for // array range )l r). Node is index // of root of current segment in segment // tree (Note that indexes in segment // tree begin with 1 for simplicity). // start and end are indexes of subarray // covered by root of current segment. static int query ( int node int start int end int l int r ) { // Completely outside the segment // returning 1 will not affect the lcm; if ( end < l || start > r ) { return 1 ; } // completely inside the segment if ( l <= start && r >= end ) { return tree [ node ]; } // partially inside int mid = ( start + end ) / 2 ; int left_lcm = query ( 2 * node start mid l r ); int right_lcm = query ( 2 * node + 1 mid + 1 end l r ); return lcm ( left_lcm right_lcm ); } // Driver code public static void Main ( String [] args ) { // initialize the array 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 the segment tree build ( 1 0 10 ); // Now we can answer each query efficiently // Print LCM of (2 5) Console . WriteLine ( query ( 1 0 10 2 5 )); // Print LCM of (5 10) Console . WriteLine ( query ( 1 0 10 5 10 )); // Print LCM of (0 10) Console . WriteLine ( query ( 1 0 10 0 10 )); } } // This code is contributed by Rajput-Ji
JavaScript < script > // LCM of given range queries using Segment Tree const MAX = 1000 // allocate space for tree var tree = new Array ( 4 * MAX ); // declaring the array globally var arr = new Array ( MAX ); // Function to return gcd of a and b function gcd ( a b ) { if ( a == 0 ) return b ; return gcd ( b % a a ); } //utility function to find lcm function lcm ( a b ) { return Math . floor ( a * b / gcd ( a b )); } // Function to build the segment tree // Node starts beginning index of current subtree. // start and end are indexes in arr[] which is global function build ( node start end ) { // If there is only one element in current subarray if ( start == end ) { tree [ node ] = arr [ start ]; return ; } let mid = Math . floor (( start + end ) / 2 ); // build left and right segments build ( 2 * node start mid ); build ( 2 * node + 1 mid + 1 end ); // build the parent let left_lcm = tree [ 2 * node ]; let right_lcm = tree [ 2 * node + 1 ]; tree [ node ] = lcm ( left_lcm right_lcm ); } // Function to make queries for array range )l r). // Node is index of root of current segment in segment // tree (Note that indexes in segment tree begin with 1 // for simplicity). // start and end are indexes of subarray covered by root // of current segment. function query ( node start end l r ) { // Completely outside the segment returning // 1 will not affect the lcm; if ( end < l || start > r ) return 1 ; // completely inside the segment if ( l <= start && r >= end ) return tree [ node ]; // partially inside let mid = Math . floor (( start + end ) / 2 ); let left_lcm = query ( 2 * node start mid l r ); let right_lcm = query ( 2 * node + 1 mid + 1 end l r ); return lcm ( left_lcm right_lcm ); } //driver function to check the above program //initialize the array 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 the segment tree build ( 1 0 10 ); // Now we can answer each query efficiently // Print LCM of (2 5) document . write ( query ( 1 0 10 2 5 ) + '
' ); // Print LCM of (5 10) document . write ( query ( 1 0 10 5 10 ) + '
' ); // Print LCM of (0 10) document . write ( query ( 1 0 10 0 10 ) + '
' ); // This code is contributed by Manoj. < /script>
Wyjście
60 15708 78540
Złożoność czasowa: O(Log N * Log n) gdzie N jest liczbą elementów w tablicy. Drugi log n oznacza czas wymagany do znalezienia LCM. Ta złożoność czasowa dotyczy każdego zapytania. Całkowita złożoność czasowa wynosi O(N + Q*Log N*log n), ponieważ zbudowanie drzewa, a następnie udzielenie odpowiedzi na zapytania wymaga czasu O(N).
Przestrzeń pomocnicza: O(N) gdzie N jest liczbą elementów w tablicy. Ta przestrzeń jest wymagana do przechowywania drzewa segmentów.
Powiązany temat: Drzewo segmentowe
Podejście nr 2: Korzystanie z matematyki
Najpierw definiujemy funkcję pomocniczą lcm(), aby obliczyć najmniejszą wspólną wielokrotność dwóch liczb. Następnie dla każdego zapytania iterujemy po podtablicy arr zdefiniowanej przez zakres zapytania i obliczamy LCM za pomocą funkcji lcm(). Wartość LCM jest przechowywana na liście, która jest zwracana jako wynik końcowy.
Drzewo segmentowe
Podejście nr 2: Korzystanie z matematyki
Algorytm
Drzewo segmentowe
Podejście nr 2: Korzystanie z matematyki
1. Zdefiniuj funkcję pomocniczą lcm(a b), aby obliczyć najmniejszą wspólną wielokrotność dwóch liczb.
2. Zdefiniuj funkcję range_lcm_queries(zapytania tablicowe), która jako dane wejściowe pobiera tablicę arr i listę zapytań o zakresy zapytań.
3. Utwórz pustą listę wyników, w której będą przechowywane wartości LCM dla każdego zapytania.
4. Dla każdego zapytania w zapytaniach wyodrębnij lewy i prawy indeks l i r.
5. Ustaw lcm_val na wartość arr[l].
6. Dla każdego indeksu i w zakresie od l+1 do r zaktualizuj lcm_val tak, aby był LCM lcm_val i arr[i] za pomocą funkcji lcm().
7. Dodaj lcm_val do listy wyników.
8. Zwróć listę wyników.
Podejście nr 2: Korzystanie z matematyki
C++ Java #include
Python /*package whatever //do not write package name here */ import java.util.ArrayList ; import java.util.List ; public class GFG { public static int gcd ( int a int b ) { if ( b == 0 ) return a ; return gcd ( b a % b ); } public static int lcm ( int a int b ) { return a * b / gcd ( a b ); } public static List < Integer > rangeLcmQueries ( List < Integer > arr List < int []> queries ) { List < Integer > results = new ArrayList <> (); for ( int [] query : queries ) { int l = query [ 0 ] ; int r = query [ 1 ] ; int lcmVal = arr . get ( l ); for ( int i = l + 1 ; i <= r ; i ++ ) { lcmVal = lcm ( lcmVal arr . get ( i )); } results . add ( lcmVal ); } return results ; } public static void main ( String [] args ) { List < Integer > arr = List . of ( 5 7 5 2 10 12 11 17 14 1 44 ); List < int []> queries = List . of ( new int [] { 2 5 } new int [] { 5 10 } new int [] { 0 10 }); List < Integer > results = rangeLcmQueries ( arr queries ); for ( int result : results ) { System . out . print ( result + ' ' ); } System . out . println (); } }
C# from math import gcd def lcm ( a b ): return a * b // gcd ( a b ) def range_lcm_queries ( arr queries ): results = [] for query in queries : l r = query lcm_val = arr [ l ] for i in range ( l + 1 r + 1 ): lcm_val = lcm ( lcm_val arr [ i ]) results . append ( lcm_val ) return results # example usage arr = [ 5 7 5 2 10 12 11 17 14 1 44 ] queries = [( 2 5 ) ( 5 10 ) ( 0 10 )] print ( range_lcm_queries ( arr queries )) # output: [60 15708 78540]
JavaScript using System ; using System.Collections.Generic ; class GFG { // Function to calculate the greatest common divisor (GCD) // using Euclidean algorithm static int GCD ( int a int b ) { if ( b == 0 ) return a ; return GCD ( b a % b ); } // Function to calculate the least common multiple (LCM) // using GCD static int LCM ( int a int b ) { return a * b / GCD ( a b ); } static List < int > RangeLcmQueries ( List < int > arr List < Tuple < int int >> queries ) { List < int > results = new List < int > (); foreach ( var query in queries ) { int l = query . Item1 ; int r = query . Item2 ; int lcmVal = arr [ l ]; for ( int i = l + 1 ; i <= r ; i ++ ) { lcmVal = LCM ( lcmVal arr [ i ]); } results . Add ( lcmVal ); } return results ; } static void Main () { List < int > arr = new List < int > { 5 7 5 2 10 12 11 17 14 1 44 }; List < Tuple < int int >> queries = new List < Tuple < int int >> { Tuple . Create ( 2 5 ) Tuple . Create ( 5 10 ) Tuple . Create ( 0 10 ) }; List < int > results = RangeLcmQueries ( arr queries ); foreach ( var result in results ) { Console . Write ( result + ' ' ); } Console . WriteLine (); } }
// JavaScript Program for the above approach // function to find out gcd function gcd ( a b ) { if ( b === 0 ) { return a ; } return gcd ( b a % b ); } // function to find out lcm function lcm ( a b ) { return ( a * b ) / gcd ( a b ); } function rangeLcmQueries ( arr queries ) { const results = []; for ( const query of queries ) { const l = query [ 0 ]; const r = query [ 1 ]; let lcmVal = arr [ l ]; for ( let i = l + 1 ; i <= r ; i ++ ) { lcmVal = lcm ( lcmVal arr [ i ]); } results . push ( lcmVal ); } return results ; } // Driver code to test above function const arr = [ 5 7 5 2 10 12 11 17 14 1 44 ]; const queries = [[ 2 5 ] [ 5 10 ] [ 0 10 ]]; const results = rangeLcmQueries ( arr queries ); for ( const result of results ) { console . log ( result + ' ' ); } console . log (); // THIS CODE IS CONTRIBUTED BY PIYUSH AGARWAL
Wyjście
[60 15708 78540]
Złożoność czasowa: O(log(min(ab))). Dla każdego zakresu zapytania iterujemy po podtablicy o rozmiarze O(n), gdzie n jest długością tablicy. Zatem złożoność czasowa całej funkcji wynosi O(qn log(min(a_i))) gdzie q to liczba zapytań, a a_i to i-ty element tablicy.
Złożoność przestrzeni: O(1), ponieważ przechowujemy tylko kilka liczb całkowitych na raz. Miejsce używane przez wejściowe tablice i zapytania nie jest brane pod uwagę.
