Rozsah dotazů LCM
Vzhledem k poli arr[] celých čísel o velikosti N a poli dotazů Q dotaz[], kde každý dotaz je typu [L R] označující rozsah od indexu L do indexu R, je úkolem najít LCM všech čísel rozsahu pro všechny dotazy.
Příklady:
Vstup: arr[] = {5 7 5 2 10 12 11 17 14 1 44}
dotaz[] = {{2 5} {5 10} {0 10}}
výstup: 6015708 78540
Vysvětlení: V prvním dotazu LCM(5 2 10 12) = 60
Ve druhém dotazu LCM(12 11 17 14 1 44) = 15708
V posledním dotazu LCM(5 7 5 2 10 12 11 17 14 1 44) = 78540Vstup: arr[] = {2 4 8 16} dotaz[] = {{2 3} {0 1}}
výstup: 16 4
Naivní přístup: Tento přístup je založen na následující matematické myšlence:
Matematicky LCM(l r) = LCM(arr[l] arr[l+1] . . . arr[r-1] arr[r]) a
LCM(a b) = (a*b) / GCD(ab)
Projděte tedy pole pro každý dotaz a vypočítejte odpověď pomocí výše uvedeného vzorce pro LCM.
Časová náročnost: O(N * Q)
Pomocný prostor: O(1)
RangeLCM Dotazy pomocí Segmentový strom :
Vzhledem k tomu, že počet dotazů může být velký, naivní řešení by bylo nepraktické. Tuto dobu lze zkrátit
V tomto problému neprobíhá žádná operace aktualizace. Můžeme tedy nejprve vytvořit strom segmentů a použít jej k zodpovězení dotazů v logaritmickém čase.
Každý uzel ve stromu by měl uložit hodnotu LCM pro tento konkrétní segment a ke kombinaci segmentů můžeme použít stejný vzorec jako výše.
Při realizaci nápadu postupujte podle níže uvedených kroků:
- Sestavte strom segmentů z daného pole.
- Procházet dotazy. Pro každý dotaz:
- Najděte tento konkrétní rozsah ve stromu segmentů.
- Pomocí výše uvedeného vzorce zkombinujte segmenty a vypočítejte LCM pro daný rozsah.
- Vytiskněte odpověď pro daný segment.
Níže je uvedena implementace výše uvedeného přístupu.
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>
Výstup
60 15708 78540
Časová náročnost: O(Log N * Log n) kde N je počet prvků v poli. Druhý log n označuje čas potřebný k nalezení LCM. Tato časová náročnost je pro každý dotaz. Celková časová složitost je O(N + Q*Log N*log n), protože čas O(N) je nutný k sestavení stromu a poté k zodpovězení dotazů.
Pomocný prostor: O(N) kde N je počet prvků v poli. Tento prostor je potřebný pro uložení stromu segmentů.
Související téma: Segmentový strom
Přístup č. 2: Použití matematiky
Nejprve definujeme pomocnou funkci lcm() pro výpočet nejmenšího společného násobku dvou čísel. Poté pro každý dotaz iterujeme podpolí arr definované rozsahem dotazu a vypočítáme LCM pomocí funkce lcm(). Hodnota LCM je uložena v seznamu, který je vrácen jako konečný výsledek.
Segmentový strom
Přístup č. 2: Použití matematiky
Algoritmus
Segmentový strom
Přístup č. 2: Použití matematiky
1. Definujte pomocnou funkci lcm(a b) pro výpočet nejmenšího společného násobku dvou čísel.
2. Definujte funkci range_lcm_queries (dotazy na pole), která jako vstup bere pole arr a seznam dotazů na rozsahy dotazů.
3. Vytvořte prázdný seznam výsledků pro uložení hodnot LCM pro každý dotaz.
4. Pro každý dotaz v dotazech extrahujte levý a pravý index la r.
5. Nastavte lcm_val na hodnotu arr[l].
6. Pro každý index i v rozsahu l+1 až r aktualizujte lcm_val na LCM lcm_val a arr[i] pomocí funkce lcm().
7. Připojte lcm_val k seznamu výsledků.
8. Vraťte seznam výsledků.
Přístup č. 2: Použití matematiky
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
Výstup
[60 15708 78540]
Časová náročnost: O(log(min(ab))). Pro každý rozsah dotazu iterujeme přes podpole o velikosti O(n), kde n je délka arr. Proto je časová složitost celkové funkce O(qn log(min(a_i))), kde q je počet dotazů a a_i je i-tý prvek arr.
Prostorová složitost: O(1), protože ukládáme pouze několik celých čísel najednou. Prostor použitý vstupním polem arr a dotazy se nebere v úvahu.
