範囲 LCM クエリ
サイズ N の整数の配列 arr[] と Q クエリの配列 query[] が与えられ、各クエリの型が [L R] でインデックス L からインデックス R までの範囲を示す場合、タスクはすべてのクエリの範囲のすべての数値の最小公倍数を見つけることです。
例:
入力： arr[] = {5 7 5 2 10 12 11 17 14 1 44}
クエリ[] = {{2 5} {5 10} {0 10}}
出力： 6015708 78540
説明： 最初のクエリでは LCM(5 2 10 12) = 60
2 番目のクエリでは、LCM(12 11 17 14 1 44) = 15708
最後のクエリでは、LCM(5 7 5 2 10 12 11 17 14 1 44) = 78540入力： arr[] = {2 4 8 16} クエリ[] = {{2 3} {0 1}}
出力： 16 4
素朴なアプローチ: このアプローチは、次の数学的考え方に基づいています。
数学的には LCM(l r) = LCM(arr[l] arr[l+1] . . . arr[r-1] arr[r]) および
LCM(a b) = (a*b) / GCD(ab)
したがって、クエリごとに配列を走査し、上記の LCM の式を使用して答えを計算します。
時間計算量: O(N * Q)
補助スペース: ○(1)
RangeLCM を使用したクエリ セグメントツリー :
クエリの数が膨大になる可能性があるため、単純な解決策は実用的ではありません。この時間は短縮できる
この問題では更新操作はありません。したがって、最初にセグメント ツリーを構築し、それを使用して対数時間でクエリに答えることができます。
ツリー内の各ノードは、その特定のセグメントの LCM 値を保存する必要があり、上記と同じ式を使用してセグメントを結合できます。
このアイデアを実装するには、以下の手順に従ってください。
- 指定された配列からセグメント ツリーを構築します。
- クエリを横断します。各クエリについて:
- セグメント ツリーでその特定の範囲を見つけます。
- 上記の式を使用してセグメントを結合し、その範囲の LCM を計算します。
- そのセグメントの答えを出力します。
以下は、上記のアプローチの実装です。
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>
出力
60 15708 78540
時間計算量: O(Log N * Log n) ここで、N は配列内の要素の数です。もう 1 つの log n は、LCM を見つけるのに必要な時間を示します。今回の複雑さはクエリごとです。合計の時間計算量は O(N + Q*Log N*log n) です。これは、ツリーを構築してクエリに応答するのに O(N) 時間が必要なためです。
補助スペース: O(N) ここで、N は配列内の要素の数です。この領域はセグメント ツリーを格納するために必要です。
関連トピック: セグメントツリー
アプローチ #2: 数学を使用する
まず、2 つの数値の最小公倍数を計算するヘルパー関数 lcm() を定義します。次に、クエリごとに、クエリ範囲で定義された arr の部分配列を反復処理し、lcm() 関数を使用して LCM を計算します。 LCM 値はリストに保存され、最終結果として返されます。
セグメントツリー
アプローチ #2: 数学を使用する
アルゴリズム
セグメントツリー
アプローチ #2: 数学を使用する
1. 2 つの数値の最小公倍数を計算するヘルパー関数 lcm(a b) を定義します。
2. 配列 arr とクエリ範囲クエリのリストを入力として受け取る関数 range_lcm_queries(arr queries) を定義します。
3. 空のリスト結果を作成して、各クエリの LCM 値を保存します。
4. クエリ内の各クエリについて、左と右のインデックス l と r を抽出します。
5. lcm_val を arr[l] の値に設定します。
6. l+1 から r の範囲内の各インデックス i について、lcm() 関数を使用して、lcm_val を lcm_val と arr[i] の LCM になるように更新します。
7. lcm_val を結果リストに追加します。
8. 結果リストを返します。
アプローチ #2: 数学を使用する
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
出力
[60 15708 78540]
時間計算量: O(log(min(ab)))。各クエリ範囲について、サイズ O(n) の部分配列を反復処理します。ここで、n は arr の長さです。したがって、関数全体の時間計算量は O(qn log(min(a_i))) になります。ここで、q はクエリの数、a_i は arr の i 番目の要素です。
空間の複雑さ: 一度に数個の整数だけを保存しているため、O(1)。入力 arr とクエリによって使用されるスペースは考慮されません。
