Chuyển Mảng Sao Cho GCD Của Mảng Trở Thành 1 Trong C++

Trong hướng dẫn này, chúng ta sẽ thảo luận chương trình chuyển đổi mảng sao cho GCD của mảng trở thành 1.

Cho một mảng và một số nguyên dương k. Nhiệm vụ là chuyển đổi các phần tử mảng sao cho GCD của các phần tử là 1, chỉ được chia các phần tử cho k bất kỳ số lần cho đến khi phần tử nhỏ hơn k.

Ví Dụ

#include <bits/stdc++.h>
using namespace std;

// Tính GCD của mảng
int calculate_gcd(int* arr, int n) {
    int gcd = arr[0];
    for (int i = 1; i < n; i++)
        gcd = __gcd(arr[i], gcd);
    return gcd;
}

// Kiểm tra có thể thực hiện phép toán không
bool convertGcd(int* arr, int n, int k) {
    int gcd = calculate_gcd(arr, n);
    int max_prime = 1;
    for (int i = 2; i <= sqrt(gcd); i++) {
        while (gcd % i == 0) {
            gcd /= i;
            max_prime = max(max_prime, i);
        }
    }
    max_prime = max(max_prime, gcd);
    return (max_prime <= k);
}

int main() {
    int arr[] = { 10, 15, 30 };
    int k = 6;
    int n = sizeof(arr) / sizeof(arr[0]);
    if (convertGcd(arr, n, k) == true)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Đầu Ra

Yes