Câu trong ảnh làm như nào các bạn ơi...

✞۝ঔৣ ☯Ma nhỏ♡♡đáng♡yêu☯ quá༺trời☯۝ঔৣ

1. Phân tích bài toán

• Yêu cầu: Cho dãy số \(A\) gồm \(N\) số nguyên dương. Bạn được phép thay đổi tối đa một số trong dãy thành một số nguyên dương bất kỳ sao cho Ước chung lớn nhất (GCD) của cả dãy sau khi thay đổi là lớn nhất có thể.

• Nhận xét: Khi ta thay đổi một số \(A_{i}\) thành một số khác, GCD của cả dãy mới chính là GCD của tất cả các số còn lại trong dãy (vì ta có thể chọn số mới là bội số của GCD đó). Do đó, bài toán quy về việc tìm giá trị lớn nhất của \(GCD(A_1, A_2, ..., A_{i-1}, A_{i+1}, ..., A_N)\) khi cho \(i\) chạy từ \(1\) đến \(N\).

2. Thuật toán

Để giải quyết bài toán với \(N\) lên đến \(5 \cdot 10^6\) trong thời gian cho phép, ta sử dụng mảng cộng dồn GCD từ hai đầu:

1. Mảng Tiền tố (L): \(L[i]\) là GCD của các số từ \(A_{1}\) đến \(A_{i}\).

o \(L[1] = A_1\)

o \(L[i] = GCD(L[i-1], A_i)\)

2. Mảng Hậu tố (R): \(R[i]\) là GCD của các số từ \(A_{i}\) đến \(A_{N}\).

o \(R[N] = A_N\)

o \(R[i] = GCD(R[i+1], A_i)\)

3. Kết quả: Duyệt qua từng vị trí \(i\) để tìm GCD của dãy khi bỏ \(A_{i}\):

o Nếu bỏ \(A_{1}\): GCD là \(R[2]\).

o Nếu bỏ \(A_{N}\): GCD là \(L[N-1]\).

o Nếu bỏ \(A_{i}\) (\(1 < i < N\)): GCD là \(GCD(L[i-1], R[i+1])\).

3. Mã nguồn tham khảo (C++)

cpp

#include <iostream>

#include <vector>

#include <numeric>

#include <algorithm>

using namespace std;

// Hàm tính GCD

long long gcd(long long a, long long b) {

while (b) {

a %= b;

swap(a, b);

}

return a;

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int n;

if (!(cin >> n)) return 0;

vector<int> a(n + 1);

for (int i = 1; i <= n; ++i) {

cin >> a[i];

}

if (n == 1) {

// Nếu chỉ có 1 số, có thể thay đổi nó thành vô cùng,

// nhưng thực tế thường lấy giá trị lớn nhất trong giới hạn hoặc chính nó.

// Theo logic đề bài "ước chung tốt nhất", kết quả có thể coi là rất lớn.

cout << a[1];

return 0;

}

vector<int> L(n + 2, 0);

vector<int> R(n + 2, 0);

for (int i = 1; i <= n; ++i) L[i] = gcd(L[i - 1], a[i]);

for (int i = n; i >= 1; --i) R[i] = gcd(R[i + 1], a[i]);

int max_gcd = 0;

for (int i = 1; i <= n; ++i) {

int current_gcd;

if (i == 1) current_gcd = R[2];

else if (i == n) current_gcd = L[n - 1];

else current_gcd = gcd(L[i - 1], R[i + 1]);

max_gcd = max(max_gcd, current_gcd);

}

cout << max_gcd << endl;

return 0;

}

Use code with caution.

Giải thích ví dụ:

• Dãy: 6 5 12 9

• Nếu bỏ 5: \(GCD(6, 12, 9) = 3\).

• Nếu bỏ 6: \(GCD(5, 12, 9) = 1\).

• Kết quả tốt nhất là 3.