Tìm số nguyên X là ước của tất cả trừ đúng một phần tử trong mảng trong C++

Khái niệm

Cho mảng số nguyên, tìm số nguyên B là ước của tất cả phần tử trừ đúng một phần tử trong mảng. UCLN của tất cả phần tử không phải 1.

Đầu vào

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

Đầu ra

8 là ước của tất cả trừ 4.

Đầu vào

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

Đầu ra

5 là ước của tất cả trừ 41.

Phương pháp

Tạo mảng tiền tố A: A[i] chứa UCLN của các phần tử từ 0 đến i. Tạo mảng hậu tố C: C[i] chứa UCLN từ i đến n-1. Nếu UCLN của A[i-1] và C[i+1] không phải ước của a[i], thì đó là đáp án.

Ví dụ

// C++ tìm ước số của tất cả trừ đúng một phần tử
#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];
    A[0] = a1[0];
    for (int i = 1; i < n1; i++) A[i] = __gcd(a1[i], A[i - 1]);
    C[n1-1] = a1[n1-1];
    for (int i = n1 - 2; i >= 0; i--) C[i] = __gcd(C[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]);
        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;
}