给出了n个数的数组，并给出了若干查询。每个查询将由两个整数l，r表示。任务是找出 GCD 数组中的所有数字中，不包括每个查询在l、r（包括两者）范围内给出的数字。 例如：
null
Input : arr[] = {2, 6, 9} Ranges [0 0], [1 1], [1 2]Output : 3 1 2 GCD of numbers excluding [0 0] or first element is GCD(6, 9) = 3GCD of numbers excluding the [1 1] orsecond element is GCD(2, 9) = 1GCD of numbers excluding [1 2] is equal to first element = 2
注： 在下面的解释中，我们使用基于1的索引 我们从一个非常基本的问题开始，如何计算两个数的GCD，最好的选择是 欧几里德算法 现在如何计算多个数字的GCD，解决方案很简单，假设有三个数字a、b和c。GCD（a、b、c）=GCD（GCD（a、b、c）。通过这种方式，我们可以很容易地找出任意数目的GCD。 一 简单的方法 为了解决每个查询的问题，假设给定的范围是l和r。取从1到l-1的数字的GCD，假设它是x，然后取从r+1到n的数字的GCD，让它是y。每个查询的输出将是GCD（x，y）。 一 有效解决方案 使用两个数组，一个作为前缀数组，另一个作为后缀数组。前缀数组的第i个索引将存储从1到i的数字的GCD，后缀数组的第i个索引将表示从i到n的数字的GCD。现在假设给定的特定查询范围是l，r，很明显，该查询的输出将是GCD（前缀[l-1]，后缀[r+1]）。
C++
// C++ program for queries of GCD excluding // given range of elements. #include<bits/stdc++.h> using namespace std; // Filling the prefix and suffix array void FillPrefixSuffix( int prefix[], int arr[], int suffix[], int n) { // Filling the prefix array following relation // prefix(i) = __gcd(prefix(i-1), arr(i)) prefix[0] = arr[0]; for ( int i=1 ;i<n; i++) prefix[i] = __gcd(prefix[i-1], arr[i]); // Filling the suffix array following the // relation suffix(i) = __gcd(suffix(i+1), arr(i)) suffix[n-1] = arr[n-1]; for ( int i=n-2; i>=0 ;i--) suffix[i] = __gcd(suffix[i+1], arr[i]); } // To calculate gcd of the numbers outside range int GCDoutsideRange( int l, int r, int prefix[], int suffix[], int n) { // If l=0, we need to tell GCD of numbers // from r+1 to n if (l==0) return suffix[r+1]; // If r=n-1 we need to return the gcd of // numbers from 1 to l if (r==n-1) return prefix[l-1]; return __gcd(prefix[l-1], suffix[r+1]); } // Driver function int main() { int arr[] = {2, 6, 9}; int n = sizeof (arr)/ sizeof (arr[0]); int prefix[n], suffix[n]; FillPrefixSuffix(prefix, arr, suffix, n); int l = 0, r = 0; cout << GCDoutsideRange(l, r, prefix, suffix, n) << endl; l = 1 ; r = 1; cout << GCDoutsideRange(l, r, prefix, suffix, n) << endl; l = 1 ; r = 2; cout << GCDoutsideRange(l, r, prefix, suffix, n) << endl; return 0; } |
JAVA
// Java program for queries of GCD excluding // given range of elements. import java.util.*; class GFG { // Calculating GCD using euclid algorithm static int GCD( int a, int b) { if (b == 0 ) return a; return GCD(b, a % b); } // Filling the prefix and suffix array static void FillPrefixSuffix( int prefix[], int arr[], int suffix[], int n) { // Filling the prefix array following relation // prefix(i) = GCD(prefix(i-1), arr(i)) prefix[ 0 ] = arr[ 0 ]; for ( int i = 1 ; i < n; i++) prefix[i] = GCD(prefix[i - 1 ], arr[i]); // Filling the suffix array following the // relation suffix(i) = GCD(suffix(i+1), arr(i)) suffix[n - 1 ] = arr[n - 1 ]; for ( int i = n - 2 ; i >= 0 ; i--) suffix[i] = GCD(suffix[i + 1 ], arr[i]); } // To calculate gcd of the numbers outside range static int GCDoutsideRange( int l, int r, int prefix[], int suffix[], int n) { // If l=0, we need to tell GCD of numbers // from r+1 to n if (l == 0 ) return suffix[r + 1 ]; // If r=n-1 we need to return the gcd of // numbers from 1 to l if (r == n - 1 ) return prefix[l - 1 ]; return GCD(prefix[l - 1 ], suffix[r + 1 ]); } // Driver code public static void main(String[] args) { int arr[] = { 2 , 6 , 9 }; int n = arr.length; int prefix[] = new int [n]; int suffix[] = new int [n]; FillPrefixSuffix(prefix, arr, suffix, n); int l = 0 , r = 0 ; System.out.println(GCDoutsideRange (l, r, prefix, suffix, n)); l = 1 ; r = 1 ; System.out.println(GCDoutsideRange (l, r, prefix, suffix, n)); l = 1 ; r = 2 ; System.out.println(GCDoutsideRange (l, r, prefix, suffix, n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program for # queries of GCD excluding # given range of elements. # Calculating GCD # using euclid algorithm def GCD(a,b): if (b = = 0 ): return a return GCD (b, a % b) # Filling the prefix # and suffix array def FillPrefixSuffix(prefix,arr,suffix,n): # Filling the prefix array # following relation # prefix(i) = GCD(prefix(i-1), arr(i)) prefix[ 0 ] = arr[ 0 ] for i in range ( 1 ,n): prefix[i] = GCD (prefix[i - 1 ], arr[i]) # Filling the suffix # array following the # relation suffix(i) = GCD(suffix(i+1), arr(i)) suffix[n - 1 ] = arr[n - 1 ] for i in range (n - 2 , - 1 , - 1 ): suffix[i] = GCD (suffix[i + 1 ], arr[i]) # To calculate gcd of # the numbers outside range def GCDoutsideRange(l,r,prefix,suffix,n): # If l=0, we need to tell GCD of numbers # from r+1 to n if (l = = 0 ): return suffix[r + 1 ] # If r=n-1 we need to return the gcd of # numbers from 1 to l if (r = = n - 1 ): return prefix[l - 1 ] return GCD(prefix[l - 1 ], suffix[r + 1 ]) # Driver code arr = [ 2 , 6 , 9 ] n = len (arr) prefix = [] suffix = [] for i in range (n + 1 ): prefix.append( 0 ) suffix.append( 0 ) FillPrefixSuffix(prefix, arr, suffix, n) l = 0 r = 0 print (GCDoutsideRange(l, r, prefix, suffix, n)) l = 1 r = 1 print (GCDoutsideRange(l, r, prefix, suffix, n)) l = 1 r = 2 print (GCDoutsideRange(l, r, prefix, suffix, n)) # This code is contributed # by Anant Agarwal. |
C#
// C# program for queries of GCD // excluding given range of elements. using System; class GFG { // Calculating GCD using // euclid algorithm static int GCD( int a, int b) { if (b == 0) return a; return GCD(b, a % b); } // Filling the prefix and suffix array static void FillPrefixSuffix( int []prefix, int []arr, int []suffix, int n) { // Filling the prefix array following // relation prefix(i) = // GCD(prefix(i - 1), arr(i)) prefix[0] = arr[0]; for ( int i = 1; i < n; i++) prefix[i] = GCD(prefix[i - 1], arr[i]); // Filling the suffix array following // the relation suffix(i) = // GCD(suffix(i+1), arr(i)) suffix[n - 1] = arr[n - 1]; for ( int i = n - 2; i >= 0; i--) suffix[i] = GCD(suffix[i + 1], arr[i]); } // To calculate gcd of the numbers outside range static int GCDoutsideRange( int l, int r, int []prefix, int []suffix, int n) { // If l=0, we need to tell // GCD of numbers from r+1 to n if (l == 0) return suffix[r + 1]; // If r=n-1 we need to return the // gcd of numbers from 1 to l if (r == n - 1) return prefix[l - 1]; return GCD(prefix[l - 1], suffix[r + 1]); } // Driver Code public static void Main() { int []arr = {2, 6, 9}; int n = arr.Length; int []prefix = new int [n]; int []suffix = new int [n]; FillPrefixSuffix(prefix, arr, suffix, n); int l = 0, r = 0; Console.WriteLine(GCDoutsideRange (l, r, prefix, suffix, n)); l = 1; r = 1; Console.WriteLine(GCDoutsideRange (l, r, prefix, suffix, n)); l = 1; r = 2; Console.Write(GCDoutsideRange (l, r, prefix, suffix, n)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP program for queries of GCD excluding // given range of elements. // Calculating GCD using euclid algorithm function GCD( $a , $b ) { if ( $b == 0) return $a ; return GCD ( $b , $a % $b ); } // Filling the prefix and suffix array function FillPrefixSuffix(& $prefix , & $arr , & $suffix , $n ) { // Filling the prefix array following relation // prefix(i) = GCD(prefix(i-1), arr(i)) $prefix [0] = $arr [0]; for ( $i = 1; $i < $n ; $i ++) $prefix [ $i ] = GCD ( $prefix [ $i - 1], $arr [ $i ]); // Filling the suffix array following the // relation suffix(i) = GCD(suffix(i+1), arr(i)) $suffix [ $n - 1] = $arr [ $n - 1]; for ( $i = $n - 2; $i >= 0 ; $i --) $suffix [ $i ] = GCD ( $suffix [ $i + 1], $arr [ $i ]); } // To calculate gcd of the numbers outside range function GCDoutsideRange( $l , $r , & $prefix , & $suffix , $n ) { // If l=0, we need to tell GCD of numbers // from r+1 to n if ( $l == 0) return $suffix [ $r + 1]; // If r=n-1 we need to return the gcd of // numbers from 1 to l if ( $r == $n - 1) return $prefix [ $l - 1]; return GCD( $prefix [ $l - 1], $suffix [ $r + 1]); } // Driver Code $arr = array (2, 6, 9); $n = sizeof( $arr ); $prefix = array_fill (0, $n , NULL); $suffix = array_fill (0, $n , NULL); FillPrefixSuffix( $prefix , $arr , $suffix , $n ); $l = 0; $r = 0; echo GCDoutsideRange( $l , $r , $prefix , $suffix , $n ) . "" ; $l = 1 ; $r = 1; echo GCDoutsideRange( $l , $r , $prefix , $suffix , $n ) . "" ; $l = 1 ; $r = 2; echo GCDoutsideRange( $l , $r , $prefix , $suffix , $n ) . "" ; // This code is contributed by ita_c ?> |
Javascript
<script> // JavaScript program for queries of GCD excluding // given range of elements. // Calculating GCD using euclid algorithm function GCD(a , b) { if (b == 0) return a; return GCD(b, a % b); } // Filling the prefix and suffix array function FillPrefixSuffix(prefix , arr , suffix , n) { // Filling the prefix array following relation // prefix(i) = GCD(prefix(i-1), arr(i)) prefix[0] = arr[0]; for (i = 1; i < n; i++) prefix[i] = GCD(prefix[i - 1], arr[i]); // Filling the suffix array following the // relation suffix(i) = GCD(suffix(i+1), arr(i)) suffix[n - 1] = arr[n - 1]; for (i = n - 2; i >= 0; i--) suffix[i] = GCD(suffix[i + 1], arr[i]); } // To calculate gcd of the numbers outside range function GCDoutsideRange(l , r , prefix , suffix , n) { // If l=0, we need to tell GCD of numbers // from r+1 to n if (l == 0) return suffix[r + 1]; // If r=n-1 we need to return the gcd of // numbers from 1 to l if (r == n - 1) return prefix[l - 1]; return GCD(prefix[l - 1], suffix[r + 1]); } // Driver code var arr = [ 2, 6, 9 ]; var n = arr.length; var prefix = Array(n).fill(0); var suffix = Array(n).fill(0); FillPrefixSuffix(prefix, arr, suffix, n); var l = 0, r = 0; document.write(GCDoutsideRange(l, r, prefix, suffix, n)); document.write( "<br>" ); l = 1; r = 1; document.write(GCDoutsideRange(l, r, prefix, suffix, n)); document.write( "<br>" ); l = 1; r = 2; document.write(GCDoutsideRange(l, r, prefix, suffix, n)); document.write( "<br>" ); // This code is contributed by todaysgaurav </script> |
输出：
312
本文由 阿尤什·贾哈 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
