# 查詢給定數組中所有數字的 GCD（給定范圍內的元素除外） > 原文： [https://www.geeksforgeeks.org/queries-gcd-numbers-array-except-elements-given-range/](https://www.geeksforgeeks.org/queries-gcd-numbers-array-except-elements-given-range/) 給定一個由`n`個數字組成的數組，并給出了多個查詢。 每個查詢將由兩個整數`l`，`r`表示。 任務是找出每個查詢的數組中所有數字的 [GCD](https://en.wikipedia.org/wiki/Greatest_common_divisor)，但不包括范圍`l`，`r`（包括兩端）中給出的數字。 **示例**： ``` 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) = 3 GCD of numbers excluding the [1 1] or second element is GCD(2, 9) = 1 GCD of numbers excluding [1 2] is equal to first element = 2 ``` **注意**：在下面的說明中，我們使用基于 1 的索引 我們從一個非常基本的問題開始，如何計算兩個數字的 GCD，最好的選擇是 [Euclid 算法](https://www.geeksforgeeks.org/basic-and-extended-euclidean-algorithms/)。 現在如何計算一個以上數字的 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(prefix[l - 1], suffix[r + 1])`。 ## C++ ```cpp // 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 // 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 folowing 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 ```py # 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 folowing 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# ```cs // 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 folowing? ????// 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? // 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 folowing 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) . "\n"; $l = 1 ; $r = 1; echo GCDoutsideRange($l, $r, $prefix, $suffix, $n) . "\n"; $l = 1 ; $r = 2; echo GCDoutsideRange($l, $r, $prefix, $suffix, $n) . "\n"; // This code is contributed by ita_c ?> ``` **輸出**： ``` 3 1 2 ```