ปรับอาร์เรย์ให้ GCD เท่ากับ 1 ใน C++

ภาพรวมปัญหา

ได้รับอาร์เรย์และ K ต้องทำให้ GCD ของอาร์เรย์ = 1 โดยหารสมาชิกด้วย K ซ้ำได้จน < K

ตัวอย่าง

Input: arr = {10, 15, 30}, k = 6
Output: Yes

วิธีแก้ปัญหา

1. หา GCD ของอาร์เรย์ทั้งหมด
2. หาเฉพาะตัวประกอบมากที่สุดของ GCD
3. ถ้าเฉพาะตัวประกอบมากที่สุด ≤ K → ทำได้ (Yes)

ตัวอย่างโค้ด C++

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

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;
}

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;
}

ผลลัพธ์ (Output)

Yes