แนวคิด
สำหรับอาร์เรย์อาร์เรย์ที่กำหนด[] ซึ่งมี GCD ขององค์ประกอบที่เป็นไปได้ทุกคู่ของอาร์เรย์อื่น หน้าที่ของเราคือกำหนดตัวเลขดั้งเดิมที่ใช้คำนวณอาร์เรย์ GCD
อินพุต
array[] = {6, 1, 1, 13} ผลลัพธ์
13 6 gcd(13, 13) = 13 gcd(13, 6) = 1 gcd(6, 13) = 1 gcd(6, 6) = 6
อินพุต
arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3} ผลลัพธ์
13 11 8 6 6
วิธีการ
-
ขั้นแรก ให้เรียงลำดับอาร์เรย์ตามลำดับที่ลดลง
-
องค์ประกอบที่ใหญ่ที่สุดจะเป็นหนึ่งในตัวเลขดั้งเดิมเสมอ รักษาหมายเลขนั้นและลบออกจากอาร์เรย์
-
คำนวณ GCD ขององค์ประกอบที่ทำในขั้นตอนก่อนหน้าโดยองค์ประกอบปัจจุบันเริ่มต้นจากค่าที่ใหญ่ที่สุดและละทิ้งค่า GCD จากอาร์เรย์ที่กำหนด
ตัวอย่าง
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Shows utility function to print
// the contents of an array
void printArr(int array[], int n1){
for (int i = 0; i < n1; i++)
cout << array[i] << " ";
}
// Shows function to determine the required numbers
void findNumbers(int array[], int n1){
// Used to sort array in decreasing order
sort(array, array + n1, greater<int>());
int freq1[array[0] + 1] = { 0 };
// Here, count frequency of each element
for (int i = 0; i < n1; i++)
freq1[array[i]]++;
// Shows size of the resultant array
int size1 = sqrt(n1);
int brr1[size1] = { 0 }, x1, l1 = 0;
for (int i = 0; i < n1; i++) {
if (freq1[array[i]] > 0) {
// Here, store the highest element in
// the resultant array
brr1[l1] = array[i];
//Used to decrement the frequency of that element
freq1[brr1[l1]]--;
l1++;
for (int j = 0; j < l1; j++) {
if (i != j) {
// Calculate GCD
x1 = __gcd(array[i], brr1[j]);
// Decrement GCD value by 2
freq1[x1] -= 2;
}
}
}
}
printArr(brr1, size1);
}
// Driver code
int main(){
/* int array[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, 6, 6, 6, 8, 11, 13, 3, 3}; */
int array[] = { 6, 1, 1, 13};
int n1 = sizeof(array) / sizeof(array[0]);
findNumbers(array, n1);
return 0;
} ผลลัพธ์
13 6
