หาจำนวนเต็ม X ที่เป็นตัวหารของทุกตัวยกเว้นหนึ่งในอาร์เรย์ C++

แนวคิด

ได้รับอาร์เรย์ของจำนวนเต็ม ให้หาจำนวนเต็ม B ที่เป็นตัวหารของทุกสมาชิกยกเว้นสมาชิกเพียงตัวเดียวในอาร์เรย์ที่กำหนด

หมายเหตุ: GCD ของทุกสมาชิกไม่ใช่ 1

อินพุต

arr[] = {8, 16, 4, 24}

เอาต์พุต

8 8 เป็นตัวหารของทุกตัวยกเว้น 4

อินพุต

arr[] = {50, 15, 40, 41}

เอาต์พุต

5 5 เป็นตัวหารของทุกตัวยกเว้น 41

วิธีการ

สร้างอาร์เรย์คำนำหน้า A ที่ตำแหน่ง i มี GCD ของสมาชิกทั้งหมดจาก 1 ถึง i อย่างเดียวกัน สร้างอาร์เรย์ต่อท้าย C ที่ดัชนี i มี GCD ของสมาชิกทั้งหมดจาก i ถึง n-1 (ดัชนีสุดท้าย) หาก GCD ของ A[i-1] และ C[i+1] ไม่ใช่ตัวหารของสมาชิกที่ i แสดงว่านี่คือคำตอบที่ต้องการ

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

// โปรแกรม C++ หาตัวหารของทุกตัวยกเว้นเพียงหนึ่งในอาร์เรย์
#include <bits/stdc++.h>
using namespace std;

// ฟังก์ชันคืนค่าตัวหารของทุกตัวยกเว้นเพียงหนึ่งในอาร์เรย์
int getDivisor1(int a1[], int n1) {
    // หากมีเพียงหนึ่งสมาชิกในอาร์เรย์
    if (n1 == 1)
        return (a1[0] + 1);
    int A[n1], C[n1];
    // สร้างอาร์เรย์คำนำหน้าของ GCD
    A[0] = a1[0];
    for (int i = 1; i < n1; i++)
        A[i] = __gcd(a1[i], A[i - 1]);
    // สร้างอาร์เรย์ต่อท้ายของ GCD
    C[n1 - 1] = a1[n1 - 1];
    for (int i = n1 - 2; i >= 0; i--)
        C[i] = __gcd(A[i + 1], a1[i]);
    // วนลูปผ่านอาร์เรย์
    for (int i = 0; i <= n1; i++) {
        // ตัวแปรเก็บตัวหาร
        int cur1;
        // หาตัวหาร
        if (i == 0)
            cur1 = C[i + 1];
        else if (i == n1 - 1)
            cur1 = A[i - 1];
        else
            cur1 = __gcd(A[i - 1], C[i + 1]);
        // ตรวจสอบว่ามันไม่ใช่ตัวหารของ a[i]
        if (a1[i] % cur1 != 0)
            return cur1;
    }
    return 0;
}

// โค้ดหลัก
int main() {
    int a1[] = {50, 15, 40, 41};
    int n1 = sizeof(a1) / sizeof(a1[0]);
    cout << getDivisor1(a1, n1);
    return 0;
}