Hiểu bài toán

Bài toán yêu cầu xác định xem hai số nguyên dương a và b có phải là một cặp 'số bạn bè' (amicable numbers) hay không. Theo định nghĩa trong đề bài, hai số được coi là 'sinh đôi' (tức là số bạn bè) nếu như tổng các ước số thực sự (không tính chính nó) của số a bằng với giá trị của số b, và đồng thời tổng các ước số thực sự của số b cũng bằng với giá trị của số a. Ví dụ: Các ước của 220 (loại trừ 220) là 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, tổng là 284. Các ước của 284 (loại trừ 284) là 1, 2, 4, 71, 142, tổng là 220. Vì vậy, 220 và 284 là một cặp số bạn bè.

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

Cách Brute Force (Duyệt toàn bộ)

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    long long sumA = 0, sumB = 0;

    // Tính tổng ước của a (không tính a)
    for (int i = 1; i < a; i++) {
        if (a % i == 0) sumA += i;
    }

    // Tính tổng ước của b (không tính b)
    for (int i = 1; i < b; i++) {
        if (b % i == 0) sumB += i;
    }

    if (sumA == b && sumB == a) cout << "YES";
    else cout << "NO";

    return 0;
}

• Time Complexity: O(a + b)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Ta sử dụng hai vòng lặp riêng biệt để duyệt từ 1 đến a-1 và từ 1 đến b-1. Trong mỗi vòng lặp, ta kiểm tra xem số đó có phải là ước của a (hoặc b) không. Nếu có, ta cộng dồn vào biến tổng tương ứng. Cuối cùng, ta chỉ cần so sánh điều kiện tổng ước của a có bằng b không và tổng ước của b có bằng a không. Tuy nhiên, với giới hạn a, b lên tới 10^9, phương pháp này sẽ bị chậm và không thể chấp nhận trong các kỳ thi lập trình cạnh tranh thực tế.

Cách Optimized Brute Force (Tối ưu vòng lặp)

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

int tinhTongUoc(int n) {
    if (n <= 1) return 0;
    int sum = 1; // 1 luôn là ước của mọi số n > 1
    int root = sqrt(n);

    // Duyệt từ 2 đến căn bậc hai của n
    for (int i = 2; i <= root; i++) {
        if (n % i == 0) {
            if (i == n / i) {
                sum += i; // Trường hợp bình phương (ví dụ 4 = 2*2)
            } else {
                sum += i + n / i; // Thêm cả cặp ước
            }
        }
    }
    return sum;
}

int main() {
    long long a, b;
    cin >> a >> b;

    if (a == b) {
        // Hai số bằng nhau chỉ có thể là bạn bè nếu là số hoàn hảo
        // (vì tổng ước phải bằng chính nó)
        // Tuy nhiên, theo ví dụ và logic bài toán, thường kiểm tra riêng
        // Solution 3 kiểm tra a==b và a,b thuộc {0,1} thì YES, ngược lại NO
        // Thực tế cặp số bạn bè phải là 2 số khác nhau.
        cout << "NO";
    } else {
        long long sumA = tinhTongUoc(a);
        long long sumB = tinhTongUoc(b);

        if (sumA == b && sumB == a) cout << "YES";
        else cout << "NO";
    }
    return 0;
}

• Time Complexity: O(sqrt(a) + sqrt(b))
• Space Complexity: O(1)

Phương pháp này cải tiến việc tính tổng ước. Thay vì duyệt từ 1 đến n, ta chỉ cần duyệt từ 1 đến căn bậc hai của n (√n). Nếu i là ước của n thì n/i cũng là ước. Điều này giảm đáng kể số lượng vòng lặp. Ví dụ với n = 10^9, số lần lặp chỉ khoảng 31,622 lần thay vì 10^9 lần. Độ phức tạp thời gian giảm từ O(N) xuống O(√N), giúp giải quyết bài toán này trong thời gian rất nhanh.

Cách Naive Iteration (Direct Loop)

#include <iostream>
using namespace std;

int main() {
    int a,b;
    cin>>a>>b;
    long long tonga=0,tongb=0;
    for(int i=1;i<a;i++)
    {
      if(a%i==0) tonga+=i;
    }
    for(int i=1;i<b;i++)
    {
      if(b%i==0) tongb+=i;
    }
    if(tonga==b && tongb==a) cout<<"YES";
    else cout<<"NO";
    return 0;
}

• Time Complexity: O(10^9)
• Space Complexity: O(1)

Đây là solution 1 và 2 trong danh sách đã cho. Nó sử dụng vòng lặp từ 1 đến a-1 và 1 đến b-1. Mặc dù code rất ngắn và dễ hiểu, nhưng nó chỉ chạy đúng với các dữ liệu đầu vào nhỏ. Với a, b lên tới 10^9, vòng lặp sẽ rất lâu và gây ra lỗi Time Limit Exceeded.

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

Bài học kinh nghiệm

• Bài toán yêu cầu kiểm tra tính chất song song: tổng ước của a bằng b VÀ tổng ước của b bằng a.
• Có thể tối ưu đáng kể thời gian tính tổng các ước số bằng cách chỉ duyệt đến căn bậc hai của số đó (√n), thay vì duyệt đến chính nó.
• Cần dùng kiểu dữ liệu long long cho biến tổng để tránh tràn số (overflow) nếu các ước số cộng lại vượt quá giới hạn của kiểu int.

Lỗi thường gặp

• Sử dụng thuật toán lặp từ 1 đến n-1 (O(N))导致 Timeout khi n lớn (ví dụ 10^9).
• Quên kiểm tra trường hợp hai số bằng nhau (a == b). Nếu a == b, để là số bạn bè thì a phải là số hoàn hảo (tổng ước = a). Tuy nhiên, định nghĩa số bạn bè thường áp dụng cho hai số khác nhau. Solution 3 đã xử lý trường hợp này một cách đặc biệt.
• Tràn số biến tổng nếu dùng kiểu int thay vì long long.