LCM และ GCD ขั้นต่ำที่เป็นไปได้ในอาร์เรย์ย่อยที่เป็นไปได้ทั้งหมดใน C++

สมมติว่าเรามีอาร์เรย์ arr ขนาด N มีตัวเลขบวก N เราต้องหาองค์ประกอบขั้นต่ำของ subarray ที่เป็นไปได้ทั้งหมด สมมติว่าอาร์เรย์คือ {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