C++で可能なすべてのサブアレイの中で可能な最小LCMおよびGCD

サイズNの配列arrがあるとします。これにはN個の正の数があります。考えられるすべてのサブアレイの最小要素を見つける必要があります。アレイが{2、66、14、521}であり、最小LCMが2、GCDが1であるとします。

貪欲なアプローチを使用してこの問題を解決します。要素の数を減らすとLCMが少なくなり、配列サイズを増やすとGCDが少なくなります。配列から最小の要素を見つける必要があります。これは単一の要素であり、LCMが必要になります。 GCDの場合、GCDはアレイのすべての要素のGCDになります。

例

#include <iostream>
#include <algorithm>
using namespace std;
int minimum_gcd(int arr[], int n) {
   int GCD = 0;
   for (int i = 0; i < n; i++)
   GCD = __gcd(GCD, arr[i]);
   return GCD;
}
int minimum_lcm(int arr[], int n) {
   int LCM = arr[0];
   for (int i = 1; i < n; i++)
   LCM = min(LCM, arr[i]);
   return LCM;
}
int main() {
   int arr[] = { 2, 66, 14, 521 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "LCM: " << minimum_lcm(arr, n) << ", GCD: " << minimum_gcd(arr, n);
}

出力

LCM: 2, GCD: 1