给定n个数的数组arr[]和整数k，求gcd等于k的最小子数组的长度。 例子：
null
Input: arr[] = {6, 9, 7, 10, 12, 24, 36, 27}, K = 3Output: 2Explanation: GCD of subarray {6,9} is 3.GCD of subarray {24,36,27} is also 3,but {6,9} is the smallest
注：以下方法的时间复杂度分析假设数字的大小是固定的，寻找两个元素的GCD需要恒定的时间。
方法1
找到所有子阵的GCD，并用GCD k跟踪最小长度子阵。其时间复杂度为O（n 3. )，O（n） 2. )对于每个子阵，O（n）用于查找子阵的gcd。
方法2
使用所讨论的基于分段树的方法查找所有子阵列的GCD 在这里 .此解决方案的时间复杂度为O（n 2. logn），O（n） 2. )对于每个子阵列和O（logn），使用段树查找子阵列的GCD。
方法3
这个想法是使用 分段树 和二进制搜索来实现时间复杂度O（n（logn） 2. ).
- 如果数组中有任何等于“k”的数字，那么答案是1，因为k的GCD是k。返回1。
- 如果没有可被k整除的数，那么GCD就不存在。返回-1。
- 如果上述情况均不成立，则最小子阵列的长度要么大于1，要么不存在GCD。在本例中，我们遵循以下步骤。
- 建立段树，以便我们可以使用讨论的方法快速找到任何子阵列的GCD 在这里
- 在建立分段树之后，将每个索引作为起点，对端点进行二值搜索，使得这两个点之间的子数组具有GCDK。
以下是上述想法的实施。
C++
// C++ Program to find GCD of a number in a given Range // using segment Trees #include <bits/stdc++.h> using namespace std; // To store segment tree int *st; // Function to find gcd of 2 numbers. int gcd( int a, int b) { if (a < b) swap(a, b); if (b==0) return a; return gcd(b, a%b); } /* A recursive function to get gcd of given range of array indexes. The following are parameters for this function. st --> Pointer to segment tree si --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0 ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[index] qs & qe --> Starting and ending indexes of query range */ int findGcd( int ss, int se, int qs, int qe, int si) { if (ss>qe || se < qs) return 0; if (qs<=ss && qe>=se) return st[si]; int mid = ss+(se-ss)/2; return gcd(findGcd(ss, mid, qs, qe, si*2+1), findGcd(mid+1, se, qs, qe, si*2+2)); } //Finding The gcd of given Range int findRangeGcd( int ss, int se, int arr[], int n) { if (ss<0 || se > n-1 || ss>se) { cout << "Invalid Arguments" << "" ; return -1; } return findGcd(0, n-1, ss, se, 0); } // A recursive function that constructs Segment Tree for // array[ss..se]. si is index of current node in segment // tree st int constructST( int arr[], int ss, int se, int si) { if (ss==se) { st[si] = arr[ss]; return st[si]; } int mid = ss+(se-ss)/2; st[si] = gcd(constructST(arr, ss, mid, si*2+1), constructST(arr, mid+1, se, si*2+2)); return st[si]; } /* Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */ int *constructSegmentTree( int arr[], int n) { int height = ( int )( ceil (log2(n))); int size = 2*( int ) pow (2, height)-1; st = new int [size]; constructST(arr, 0, n-1, 0); return st; } // Returns size of smallest subarray of arr[0..n-1] // with GCD equal to k. int findSmallestSubarr( int arr[], int n, int k) { // To check if a multiple of k exists. bool found = false ; // Find if k or its multiple is present for ( int i=0; i<n; i++) { // If k is present, then subarray size is 1. if (arr[i] == k) return 1; // Break the loop to indicate presence of a // multiple of k. if (arr[i] % k == 0) found = true ; } // If there was no multiple of k in arr[], then // we can't get k as GCD. if (found == false ) return -1; // If there is a multiple of k in arr[], build // segment tree from given array constructSegmentTree(arr, n); // Initialize result int res = n+1; // Now consider every element as starting point // and search for ending point using Binary Search for ( int i=0; i<n-1; i++) { // a[i] cannot be a starting point, if it is // not a multiple of k. if (arr[i] % k != 0) continue ; // Initialize indexes for binary search of closest // ending point to i with GCD of subarray as k. int low = i+1; int high = n-1; // Initialize closest ending point for i. int closest = 0; // Binary Search for closest ending point // with GCD equal to k. while ( true ) { // Find middle point and GCD of subarray // arr[i..mid] int mid = low + (high-low)/2; int gcd = findRangeGcd(i, mid, arr, n); // If GCD is more than k, look further if (gcd > k) low = mid; // If GCD is k, store this point and look for // a closer point else if (gcd == k) { high = mid; closest = mid; } // If GCD is less than, look closer else high = mid; // If termination condition reached, set // closest if ( abs (high-low) <= 1) { if (findRangeGcd(i, low, arr, n) == k) closest = low; else if (findRangeGcd(i, high, arr, n)==k) closest = high; break ; } } if (closest != 0) res = min(res, closest - i + 1); } // If res was not changed by loop, return -1, // else return its value. return (res == n+1) ? -1 : res; } // Driver program to test above functions int main() { int n = 8; int k = 3; int arr[] = {6, 9, 7, 10, 12, 24, 36, 27}; cout << "Size of smallest sub-array with given" << " size is " << findSmallestSubarr(arr, n, k); return 0; } |
JAVA
// Java Program to find GCD of a number in a given Range // using segment Trees class GFG { // To store segment tree static int []st; // Function to find gcd of 2 numbers. static int gcd( int a, int b) { if (a < b) swap(a, b); if (b == 0 ) return a; return gcd(b, a % b); } private static void swap( int x, int y) { int temp = x; x = y; y = temp; } /* A recursive function to get gcd of given range of array indexes. The following are parameters for this function. st --> Pointer to segment tree si --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0 ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[index] qs & qe --> Starting and ending indexes of query range */ static int findGcd( int ss, int se, int qs, int qe, int si) { if (ss > qe || se < qs) return 0 ; if (qs <= ss && qe >= se) return st[si]; int mid = ss + (se - ss) / 2 ; return gcd(findGcd(ss, mid, qs, qe, si * 2 + 1 ), findGcd(mid + 1 , se, qs, qe, si * 2 + 2 )); } // Finding The gcd of given Range static int findRangeGcd( int ss, int se, int arr[], int n) { if (ss < 0 || se > n- 1 || ss > se) { System.out.println( "Invalid Arguments" ); return - 1 ; } return findGcd( 0 , n - 1 , ss, se, 0 ); } // A recursive function that constructs Segment Tree for // array[ss..se]. si is index of current node in segment // tree st static int constructST( int arr[], int ss, int se, int si) { if (ss == se) { st[si] = arr[ss]; return st[si]; } int mid = ss + (se - ss) / 2 ; st[si] = gcd(constructST(arr, ss, mid, si * 2 + 1 ), constructST(arr, mid+ 1 , se, si * 2 + 2 )); return st[si]; } /* Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */ static int []constructSegmentTree( int arr[], int n) { int height = ( int )(Math.ceil(Math.log(n))); int size = 2 *( int )Math.pow( 2 , height) - 1 ; st = new int [size]; constructST(arr, 0 , n - 1 , 0 ); return st; } // Returns size of smallest subarray of arr[0..n-1] // with GCD equal to k. static int findSmallestSubarr( int arr[], int n, int k) { // To check if a multiple of k exists. boolean found = false ; // Find if k or its multiple is present for ( int i = 0 ; i < n; i++) { // If k is present, then subarray size is 1. if (arr[i] == k) return 1 ; // Break the loop to indicate presence of a // multiple of k. if (arr[i] % k == 0 ) found = true ; } // If there was no multiple of k in arr[], then // we can't get k as GCD. if (found == false ) return - 1 ; // If there is a multiple of k in arr[], build // segment tree from given array constructSegmentTree(arr, n); // Initialize result int res = n + 1 ; // Now consider every element as starting point // and search for ending point using Binary Search for ( int i = 0 ; i < n - 1 ; i++) { // a[i] cannot be a starting point, if it is // not a multiple of k. if (arr[i] % k != 0 ) continue ; // Initialize indexes for binary search of closest // ending point to i with GCD of subarray as k. int low = i + 1 ; int high = n - 1 ; // Initialize closest ending point for i. int closest = 0 ; // Binary Search for closest ending point // with GCD equal to k. while ( true ) { // Find middle point and GCD of subarray // arr[i..mid] int mid = low + (high-low)/ 2 ; int gcd = findRangeGcd(i, mid, arr, n); // If GCD is more than k, look further if (gcd > k) low = mid; // If GCD is k, store this point and look for // a closer point else if (gcd == k) { high = mid; closest = mid; } // If GCD is less than, look closer else high = mid; // If termination condition reached, set // closest if (Math.abs(high-low) <= 1 ) { if (findRangeGcd(i, low, arr, n) == k) closest = low; else if (findRangeGcd(i, high, arr, n)==k) closest = high; break ; } } if (closest != 0 ) res = Math.min(res, closest - i + 1 ); } // If res was not changed by loop, return -1, // else return its value. return (res == n+ 1 ) ? - 1 : res; } // Driver code public static void main(String args[]) { int n = 8 ; int k = 3 ; int arr[] = { 6 , 9 , 7 , 10 , 12 , 24 , 36 , 27 }; System.out.println( "Size of smallest sub-array with given" + " size is " + findSmallestSubarr(arr, n, k)); } } // This code is contributed by Rajput-Ji |
Python3
# Python Program to find GCD of a number in a given Range # using segment Trees # To store segment tree st = [] # Function to find gcd of 2 numbers. def gcd(a: int , b: int ) - > int : if a < b: a, b = b, a if b = = 0 : return a return gcd(b, a % b) # A recursive function to get gcd of given # range of array indexes. The following are parameters for # this function. # st --> Pointer to segment tree # si --> Index of current node in the segment tree. Initially # 0 is passed as root is always at index 0 # ss & se --> Starting and ending indexes of the segment # represented by current node, i.e., st[index] # qs & qe --> Starting and ending indexes of query range def findGcd(ss: int , se: int , qs: int , qe: int , si: int ) - > int : if ss > qe or se < qs: return 0 if qs < = ss and qe > = se: return st[si] mid = ss + (se - ss) / / 2 return gcd(findGcd(ss, mid, qs, qe, si * 2 + 1 ), findGcd(mid + 1 , se, qs, qe, si * 2 + 2 )) # Finding The gcd of given Range def findRangeGcd(ss: int , se: int , arr: list , n: int ) - > int : if ss < 0 or se > n - 1 or ss > se: print ( "invalid Arguments" ) return - 1 return findGcd( 0 , n - 1 , ss, se, 0 ) # A recursive function that constructs Segment Tree for # array[ss..se]. si is index of current node in segment # tree st def constructST(arr: list , ss: int , se: int , si: int ) - > int : if ss = = se: st[si] = arr[ss] return st[si] mid = ss + (se - ss) / / 2 st[si] = gcd(constructST(arr, ss, mid, si * 2 + 1 ), constructST(arr, mid + 1 , se, si * 2 + 2 )) return st[si] # Function to construct segment tree from given array. # This function allocates memory for segment tree and # calls constructSTUtil() to fill the allocated memory def constructSegmentTree(arr: list , n: int ) - > list : global st from math import ceil, log2, pow height = int (ceil(log2(n))) size = 2 * int ( pow ( 2 , height)) - 1 st = [ 0 ] * size constructST(arr, 0 , n - 1 , 0 ) return st # Returns size of smallest subarray of arr[0..n-1] # with GCD equal to k. def findSmallestSubarr(arr: list , n: int , k: int ) - > int : # To check if a multiple of k exists. found = False # Find if k or its multiple is present for i in range (n): # If k is present, then subarray size is 1. if arr[i] = = k: return 1 # Break the loop to indicate presence of a # multiple of k. if arr[i] % k = = 0 : found = True # If there was no multiple of k in arr[], then # we can't get k as GCD. if found = = False : return - 1 # If there is a multiple of k in arr[], build # segment tree from given array constructSegmentTree(arr, n) # Initialize result res = n + 1 # Now consider every element as starting point # and search for ending point using Binary Search for i in range (n - 1 ): # a[i] cannot be a starting point, if it is # not a multiple of k. if arr[i] % k ! = 0 : continue # Initialize indexes for binary search of closest # ending point to i with GCD of subarray as k. low = i + 1 high = n - 1 # Initialize closest ending point for i. closest = 0 # Binary Search for closest ending point # with GCD equal to k. while True : # Find middle point and GCD of subarray # arr[i..mid] mid = low + (high - low) / / 2 gcd = findRangeGcd(i, mid, arr, n) # If GCD is more than k, look further if gcd > k: low = mid # If GCD is k, store this point and look for # a closer point else if gcd = = k: high = mid closest = mid # If GCD is less than, look closer else : high = mid # If termination condition reached, set # closest if abs (high - low) < = 1 : if findRangeGcd(i, low, arr, n) = = k: closest = low else if findRangeGcd(i, high, arr, n) = = k: closest = high break if closest ! = 0 : res = min (res, closest - i + 1 ) # If res was not changed by loop, return -1, # else return its value. return - 1 if res = = n + 1 else res # Driver Code if __name__ = = "__main__" : n = 8 k = 3 arr = [ 6 , 9 , 7 , 10 , 12 , 24 , 36 , 27 ] print ( "Size of smallest sub-array with given size is" , findSmallestSubarr(arr, n, k)) # This code is contributed by # sanjeev2552 |
C#
// C# Program to find GCD of a number in a given Range // using segment Trees using System; class GFG { // To store segment tree static int []st; // Function to find gcd of 2 numbers. static int gcd( int a, int b) { if (a < b) swap(a, b); if (b == 0) return a; return gcd(b, a % b); } private static void swap( int x, int y) { int temp = x; x = y; y = temp; } /* A recursive function to get gcd of given range of array indexes. The following are parameters for this function. st --> Pointer to segment tree si --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0 ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[index] qs & qe --> Starting and ending indexes of query range */ static int findGcd( int ss, int se, int qs, int qe, int si) { if (ss > qe || se < qs) return 0; if (qs <= ss && qe >= se) return st[si]; int mid = ss + (se - ss) / 2; return gcd(findGcd(ss, mid, qs, qe, si * 2 + 1), findGcd(mid + 1, se, qs, qe, si * 2 + 2)); } // Finding The gcd of given Range static int findRangeGcd( int ss, int se, int []arr, int n) { if (ss < 0 || se > n-1 || ss > se) { Console.WriteLine( "Invalid Arguments" ); return -1; } return findGcd(0, n - 1, ss, se, 0); } // A recursive function that constructs Segment Tree for // array[ss..se]. si is index of current node in segment // tree st static int constructST( int []arr, int ss, int se, int si) { if (ss == se) { st[si] = arr[ss]; return st[si]; } int mid = ss + (se - ss) / 2; st[si] = gcd(constructST(arr, ss, mid, si * 2 + 1), constructST(arr, mid+1, se, si * 2 + 2)); return st[si]; } /* Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */ static int []constructSegmentTree( int []arr, int n) { int height = ( int )(Math.Ceiling(Math.Log(n))); int size = 2*( int )Math.Pow(2, height) - 1; st = new int [size]; constructST(arr, 0, n - 1, 0); return st; } // Returns size of smallest subarray of arr[0..n-1] // with GCD equal to k. static int findSmallestSubarr( int []arr, int n, int k) { // To check if a multiple of k exists. bool found = false ; // Find if k or its multiple is present for ( int i = 0; i < n; i++) { // If k is present, then subarray size is 1. if (arr[i] == k) return 1; // Break the loop to indicate presence of a // multiple of k. if (arr[i] % k == 0) found = true ; } // If there was no multiple of k in arr[], then // we can't get k as GCD. if (found == false ) return -1; // If there is a multiple of k in arr[], build // segment tree from given array constructSegmentTree(arr, n); // Initialize result int res = n + 1; // Now consider every element as starting point // and search for ending point using Binary Search for ( int i = 0; i < n - 1; i++) { // a[i] cannot be a starting point, if it is // not a multiple of k. if (arr[i] % k != 0) continue ; // Initialize indexes for binary search of closest // ending point to i with GCD of subarray as k. int low = i + 1; int high = n - 1; // Initialize closest ending point for i. int closest = 0; // Binary Search for closest ending point // with GCD equal to k. while ( true ) { // Find middle point and GCD of subarray // arr[i..mid] int mid = low + (high-low)/2; int gcd = findRangeGcd(i, mid, arr, n); // If GCD is more than k, look further if (gcd > k) low = mid; // If GCD is k, store this point and look for // a closer point else if (gcd == k) { high = mid; closest = mid; } // If GCD is less than, look closer else high = mid; // If termination condition reached, set // closest if (Math.Abs(high-low) <= 1) { if (findRangeGcd(i, low, arr, n) == k) closest = low; else if (findRangeGcd(i, high, arr, n)==k) closest = high; break ; } } if (closest != 0) res = Math.Min(res, closest - i + 1); } // If res was not changed by loop, return -1, // else return its value. return (res == n+1) ? -1 : res; } // Driver code public static void Main(String []args) { int n = 8; int k = 3; int []arr = {6, 9, 7, 10, 12, 24, 36, 27}; Console.WriteLine( "Size of smallest sub-array with given" + " size is " + findSmallestSubarr(arr, n, k)); } } /* This code is contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript Program to find GCD of a number in a given Range // using segment Trees // To store segment tree var st = []; // Function to find gcd of 2 numbers. function gcd(a, b) { if (a < b) [a, b] = [b,a]; if (b == 0) return a; return gcd(b, a % b); } /* A recursive function to get gcd of given range of array indexes. The following are parameters for this function. st --> Pointer to segment tree si --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0 ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[index] qs & qe --> Starting and ending indexes of query range */ function findGcd(ss, se, qs, qe, si) { if (ss > qe || se < qs) return 0; if (qs <= ss && qe >= se) return st[si]; var mid = ss + parseInt((se - ss) / 2); return gcd(findGcd(ss, mid, qs, qe, si * 2 + 1), findGcd(mid + 1, se, qs, qe, si * 2 + 2)); } // Finding The gcd of given Range function findRangeGcd(ss, se, arr, n) { if (ss < 0 || se > n-1 || ss > se) { document.write( "Invalid Arguments" ); return -1; } return findGcd(0, n - 1, ss, se, 0); } // A recursive function that constructs Segment Tree for // array[ss..se]. si is index of current node in segment // tree st function constructST(arr, ss, se, si) { if (ss == se) { st[si] = arr[ss]; return st[si]; } var mid = ss + parseInt((se - ss) / 2); st[si] = gcd(constructST(arr, ss, mid, si * 2 + 1), constructST(arr, mid+1, se, si * 2 + 2)); return st[si]; } /* Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */ function constructSegmentTree(arr, n) { var height = parseInt(Math.ceil(Math.log(n))); var size = 2*parseInt(Math.pow(2, height)) - 1; st = Array(size).fill(0); constructST(arr, 0, n - 1, 0); return st; } // Returns size of smallest subarray of arr[0..n-1] // with GCD equal to k. function findSmallestSubarr(arr, n, k) { // To check if a multiple of k exists. var found = false ; // Find if k or its multiple is present for ( var i = 0; i < n; i++) { // If k is present, then subarray size is 1. if (arr[i] == k) return 1; // Break the loop to indicate presence of a // multiple of k. if (arr[i] % k == 0) found = true ; } // If there was no multiple of k in arr[], then // we can't get k as GCD. if (found == false ) return -1; // If there is a multiple of k in arr[], build // segment tree from given array constructSegmentTree(arr, n); // Initialize result var res = n + 1; // Now consider every element as starting point // and search for ending point using Binary Search for ( var i = 0; i < n - 1; i++) { // a[i] cannot be a starting point, if it is // not a multiple of k. if (arr[i] % k != 0) continue ; // Initialize indexes for binary search of closest // ending point to i with GCD of subarray as k. var low = i + 1; var high = n - 1; // Initialize closest ending point for i. var closest = 0; // Binary Search for closest ending point // with GCD equal to k. while ( true ) { // Find middle point and GCD of subarray // arr[i..mid] var mid = low + parseInt((high-low)/2); var gcd = findRangeGcd(i, mid, arr, n); // If GCD is more than k, look further if (gcd > k) low = mid; // If GCD is k, store this point and look for // a closer point else if (gcd == k) { high = mid; closest = mid; } // If GCD is less than, look closer else high = mid; // If termination condition reached, set // closest if (Math.abs(high-low) <= 1) { if (findRangeGcd(i, low, arr, n) == k) closest = low; else if (findRangeGcd(i, high, arr, n)==k) closest = high; break ; } } if (closest != 0) res = Math.min(res, closest - i + 1); } // If res was not changed by loop, return -1, // else return its value. return (res == n+1) ? -1 : res; } // Driver code var n = 8; var k = 3; var arr = [6, 9, 7, 10, 12, 24, 36, 27]; document.write( "Size of smallest sub-array with given" + " size is " + findSmallestSubarr(arr, n, k)); // This code is contributed by itsok. </script> |
输出
Size of smallest sub-array with given size is 2
例子：
arr[] = {6, 9, 7, 10, 12, 24, 36, 27}, K = 3// Initial value of minLen is equal to size // of arrayminLen = 8 No element is equal to k so result is either greater than 1 or doesn't exist.
第一索引
- 从1到5的子阵列的GCD为1。
- GCD
- 从1到3的子阵列的GCD为1。
- GCD
- 子阵1到2的GCD为3
- minLen=最小值（8，2）=2
第二个索引
- 从2到5的子阵列的GCD为1
- GCD
- 从2到4的子阵列的GCD为1
- GCD
- 子阵从6到8的GCD为3
- minLen=最小值（2，3）=2。
.
.
.
第六指数
- 从6到7的子阵列的GCD为12
- GCD>k
- 子阵从6到8的GCD为3
- minLen=最小值（2，3）=2
时间复杂性： O（n（logn） 2. )，O（n）表示遍历到每个索引，O（logn）表示每个子阵列，O（logn）表示每个子阵列的GCD。 本文由 尼希尔·特克瓦尼。 如果你喜欢GeekSforgeks，并且想贡献自己的力量，你也可以写一篇文章，然后把你的文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
