C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で指定された配列の要素の階乗のGCDを検索します

N個の要素を持つ配列Aがあるとします。配列のすべての要素の階乗のGCDを見つける必要があります。要素が{3、4、8、6}であるとすると、階乗のGCDは6です。ここでトリックを確認します。 2つの数値のGCDは、両方の数値を除算する最大の数値であるため、2つの数値の階乗のGCDは、最小の数値自体の階乗の値です。だから3の公約数！と5！ 3です！ =6.

例

#include <iostream>
using namespace std;
long fact(int n){
   if(n <= 1)
      return 1;
   return n * fact(n-1);
}
int gcd(int arr[], int n) {
   int min = arr[0];
   for (int i = 1; i < n; i++) {
      if(min > arr[i])
         min = arr[i];
   }
   return fact(min);
}
int main() {
   int arr[] = {3, 4, 8, 6};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "GCD: "<< gcd(arr, n);
}

出力

GCD: 6

  1. C++で連続する要素のXORを使用して配列の要素を検索する

    n個の要素のリストを見つける必要があると考えてください。ただし、実際の配列の2つの連続する要素のXOR値があります。また、実際の最初の要素が示されています。したがって、配列要素がa、b、c、d、e、fの場合、指定された配列はa ^ b、b ^ c、c ^ d、d ^ e、およびe^fになります。 aという名前の最初の番号が与えられているので、すべての番号を見つけるのに役立ちます。実際の配列の2番目の要素を検索する場合は、b =a ^ arr [i]を実行する必要があり、2番目の要素c =b ^arr[1]などを実行する必要があります。 例 #include<iostream> u

  2. C++の配列で最大GCDのペアを検索します

    正の整数の配列があるとします。私たちのタスクは、GCD値が最大である配列から整数のペアを見つけることです。 A ={1、2、3、4、5}とすると、出力は2になります。ペア（2、4）にはGCD 2があり、他のGCD値は2未満です。 この問題を解決するために、各要素の除数の数を格納するためのカウント配列を維持します。除数を数えるプロセスには、O（sqrt（arr [i]））の時間がかかります。全体をトラバースした後、最後のインデックスから最初のインデックスまでカウント配列をトラバースできます。要素が1より大きい値が見つかった場合、これは2つの要素の約数であり、最大GCDでもあることを意味します。