在C ++中从给定数组中的连续元素的GCD构造一个数组

Z时代
2024-01-10
分类：综合

假设我们有一个包含n个元素的数组A []。我们必须找到另一个数组B []，其大小为n + 1，这样B [i]和B [i + 1]的GCD为A [i]。如果有多个解决方案，则打印其中一个数组总和最小的解决方案。因此，如果A = [1,2,3]，则输出将为[1,2,6,3]

当A只有一个元素时说K，则B = [K，K]。因此B [0]将为A [0]。现在考虑完成索引i的工作，因此我们已经处理了索引i，并计算了B [i + 1]。现在，B [i + 1]和B [i + 2]的GCD = A [i +1]，然后B [i + 2]和B [i + 3]的GCD = A [i + 2]。因此B [i + 2]> = A [i + 1]，A [i + 2]的LCM。因为我们需要最小值总和，所以我们要获得B [i + 2]的最小值，所以B [i + 2] – A [i + 2]和A [i + 3]的LCM

示例

#include <iostream>
#include <algorithm>
using namespace std;
int getLCM(int a, int b) {
   return (a * b) / __gcd(a, b);
}
void gcdArray(int A[], int n) {
   cout << A[0] << " ";
   for (int i = 0; i < n - 1; i++)
   cout << getLCM(A[i], A[i + 1]) << " ";
   cout << A[n - 1];
}
int main() {
   int A[] = { 1, 2, 3 };
   int n = sizeof(A) / sizeof(A[0]);
   cout << "Constructed array: ";
   gcdArray(A, n);
}