Hiểu bài toán

Cho một dãy số nguyên dương A gồm N phần tử. Tìm tổng lớn nhất có thể của các ước chung lớn nhất (UCLN) của tất cả các cặp số hạng liên tiếp trong dãy. Cụ thể, ta cần tính tổng S = UCLN(A[1], A[2]) + UCLN(A[2], A[3]) + ... + UCLN(A[N-1], A[N]). Đây là bài toán 'TỔNG ƯỚC CHUNG LỚN NHẤT 2 SỐ HẠNG LIÊN TIẾP' (thptqh_sohoc4).

Các cách tiếp cận

Cách Mô phỏng trực tiếp (Naive)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("UCLN.Inp", "r", stdin);
    freopen("UCLN.Out", "w", stdout);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long sum = 0;
    for (int i = 0; i < n - 1; i++) {
        sum += __gcd(a[i], a[i+1]);
    }

    cout << sum;
    return 0;
}

• Time Complexity: O(N * log(V)) - V là giá trị lớn nhất của phần tử, do hàm gcd có độ phức tạp log(V).
• Space Complexity: O(N) - Để lưu dãy số.

Đây là cách tiếp cận đơn giản nhất. Ta chỉ cần duyệt qua mảng từ phần tử đầu tiên đến phần tử áp chót. Với mỗi phần tử a[i], ta tính UCLN của nó với phần tử tiếp theo a[i+1] rồi cộng dồn vào tổng. Sử dụng hàm có sẵn __gcd (hoặc std::gcd trong C++17) để tính UCLN.

Cách Tối ưu nhập xuất và xử lý

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("UCLN.Inp", "r", stdin);
    freopen("UCLN.Out", "w", stdout);

    long long n;
    cin >> n;

    if (n < 2) {
        cout << 0;
        return 0;
    }

    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    long long sum = 0;
    for (int i = 1; i < n; i++) {
        sum += gcd(a[i-1], a[i]);
    }

    cout << sum;
    return 0;
}

• Time Complexity: O(N * log(V))
• Space Complexity: O(N)

Các giải pháp được chấp nhận trong bài này đều có cùng logic tính toán O(N). Tuy nhiên, giải pháp này tập trung vào các chi tiết kỹ thuật để đảm bảo chạy đúng và nhanh trong môi trường thi đấu:

1. ios_base::sync_with_stdio(false); cin.tie(NULL);: Tắt đồng bộ hóa với stdio và bỏ ràng buộc flush trước mỗi cin, giúp nhập xuất nhanh hơn đáng kể với dữ liệu lớn.
2. Kiểu dữ liệu long long: Đảm bảo không bị tràn số nếu tổng các UCLN vượt quá giới hạn của int.
3. Kiểm tra điều kiện N < 2: Tránh lỗi truy cập ngoài mảng và logic rỗng.
4. Duyệt từ phần tử thứ 2 (hoặc dùng index i-1 và i) để tính toán.

Cách Xử lý số lớn (Big Integer) - Phân tích thừa số nguyên tố

// Pseudocode logic cho hướng giải quyết này
// Thực tế trong contest school, N và A[i] thường không quá lớn để cần giải pháp này.
// Tuy nhiên, nếu A[i] ~ 10^18 và N rất lớn, hoặc yêu cầu chia modulo, ta dùng cách này.

/*
void solve() {
    ll n; cin >> n;
    vector<ll> a(n);
    for(auto &x : a) cin >> x;

    // Giả sử ta cần chia tổng cho 10^9 + 7
    ll MOD = 1e9 + 7;
    ll sum = 0;

    // Sử dụng __int128 hoặc phân tích thừa số để tính gcd nếu cần độ chính xác tuyệt đối
    // Nhưng với C++ hiện đại, __gcd cho 64-bit integer là đủ.

    for(int i = 0; i < n - 1; i++) {
        ll g = gcd(a[i], a[i+1]);
        sum = (sum + g) % MOD; // Nếu yêu cầu chia lấy dư
    }
    cout << sum << endl;
}
*/

• Time Complexity: O(N * log(V))
• Space Complexity: O(N)

Giải pháp này về cơ bản là giống giải pháp 1 và 2 về thuật toán (tính tổng gcd liên tiếp). Tuy nhiên, 'Phân tích thừa số nguyên tố' là một hướng suy luận khác để hiểu bản chất của UCLN, hoặc để xử lý trong các trường hợp đặc biệt (số quá lớn, cần tính tổng theo modulo). Trong bài này, do đầu vào là số nguyên thông thường, cách dùng hàm __gcd có sẵn là tối ưu nhất về mặt lập trình. Tên gọi 'Phân tích thừa số nguyên tố' ở đây được dùng để chỉ nhận diện rằng UCLN là tích các thừa số chung, nhưng trong code thực thi thì thuật toán Euclid vẫn được ưu tiên.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là một bài toán mô phỏng đơn giản: tính tổng UCLN của các cặp phần tử liền kề.
• UCLN(a, b) = UCLN(b, a) và UCLN(a, b, c) = UCLN(UCLN(a, b), c). Tuy nhiên, bài này chỉ yêu cầu tổng các cặp đôi liên tiếp, không phải UCLN của cả dãy.
• Sử dụng hàm __gcd(a, b) có sẵn trong thư viện <bits/stdc++.h> (hoặc std::gcd trong C++17) là cách hiệu quả và chuẩn xác nhất để tính UCLN.

Lỗi thường gặp

• Lỗi tràn số nguyên (Integer Overflow): Nếu dùng int để lưu tổng, nhưng tổng các UCLN có thể vượt quá 2*10^9. Cần dùng long long.
• Lỗi truy cập ngoài mảng (Index Out of Bounds): Khi duyệt vòng lặp, cần đảm bảo chỉ chạy từ i = 0 đến i = N-2 (hoặc i = 1 đến N-1 với index i-1).
• Quên xử lý trường hợp N = 1: Nếu N=1, không có cặp số hạng liên tiếp nào, tổng phải là 0. Vòng lặp for(int i=0; i<n-1; i++) sẽ không chạy nếu n=1, kết quả là biến sum chưa được khởi tạo (nếu khai báo không gán giá trị) hoặc đúng là 0 (nếu khai báo = 0). Nên luôn khởi tạo biến tổng bằng 0.