Hiểu bài toán

Yêu cầu đếm số lượng số 'gần hoàn hảo' trong một dãy số. Một số được gọi là gần hoàn hảo nếu nó khác 1 (vì 1 không phải là số gần hoàn hảo theo định nghĩa bài toán) và tổng các ước số của nó (bao gồm cả chính nó) nhỏ hơn hai lần số đó. Ví dụ: số 9 có các ước là 1, 3, 9, tổng là 13, và 13 < 2*9 = 18, nên 9 là số gần hoàn hảo. Với N lên tới 100,000 và giá trị các số a_i lên tới 10,000, chúng ta cần một giải pháp hiệu quả để tính tổng các ước cho nhiều số.

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

Cách Brute Force

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long n,dem=0,i,a,j,tong=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a;
        tong=0;
        for(j=1;j<=sqrt(a);j++)
        {
            if(a%j==0)
            {
                if(a/j!=j)
                {
                    tong+=a/j+j;
                }
                else
                    tong+=a/j;
            }
        }
        if(tong<2*a and a!=1)
            {
                dem++;
            }
    }
    cout<<dem;
}

• Time Complexity: O(N * sqrt(A)), với A là giá trị lớn nhất của a_i (10^4). Với N=10^5, tổng số phép chia khoảng 10^5 * 100 = 10^7, chạy trong thời gian chấp nhận được.
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất. Với mỗi số a trong dãy, ta duyệt từ j = 1 đến sqrt(a) để tìm các ước. Nếu j là ước của a thì a/j cũng là ước. Ta cộng dồn vào biến tổng. Cuối cùng kiểm tra điều kiện tổng < 2*a và a != 1. Cách này tốn thời gian tính toán lại tổng các ước cho mỗi số xuất hiện trong dãy, ngay cả khi số đó xuất hiện nhiều lần.

Cách Sàng Sieve (Precomputation)

#include <iostream>
using namespace std;
int main()
{
    long long n,a[100000],c[100000],dem=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=100000;i++)
    {
      c[i]=0;
    }
    for(int i=1;i<=100000;i++)
    {
        for(int j=1;j<=100000/i;j++)
        {
            c[i*j]+=i;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=1)
        {
            if(c[a[i]]<2*a[i])
            {
                dem++;
            }
        }
    }
    cout<<dem;
    return 0;
}

• Time Complexity: O(A log A + N), với A = 10^5 (giới hạn mảng c). Vòng lặp sàng mất khoảng A/1 + A/2 + ... + A/A = A * log(A). Với A=10^5, thời gian chạy cực nhanh.
• Space Complexity: O(A)

Thay vì tính tổng các ước mỗi khi cần, ta precompute (tính trước) tổng các ước cho tất cả các số từ 1 đến giới hạn tối đa (ví dụ 100,000). Ta sử dụng kỹ thuật tương tự sàng Eratosthenes: với mỗi số i, ta thêm i vào tổng các ước của tất cả các bội số của nó (i, 2i, 3i...). Mảng c[x] sẽ lưu tổng các ước của x. Sau đó, với mỗi số trong input, ta chỉ cần tra cứu mảng c và kiểm tra điều kiện. Đây là cách hiệu quả nhất cho các bài toán tính tổng các ước với nhiều truy vấn.

Cách Tối ưu với Hash Map

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t,dem=0;
ll tong(ll n){
    ll s=0;
    for(ll i=1;i<=sqrt(n);i++){
        if(n%i==0){
            s+=i;
            ll j=n/i;
            s+=j;
        }
    }
    return s;
}
ll cp(ll n){
    ll s=sqrt(n);
    if(s*s!=n){
        s=0;
    }
    return s;
}
int main()
{
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        ll tong1=tong(n)-cp(n);
        if(tong1<n*2 && n!=1){
            dem++;
        }
    }
    cout<<dem;
    return 0;
}

• Time Complexity: O(N * sqrt(A)) trong trường hợp xấu nhất (nếu không dùng map), hoặc O(N * sqrt(A) + M) nếu dùng map để lưu kết quả tính toán.
• Space Complexity: O(N) hoặc O(M) (số lượng số phân biệt)

Phương pháp này (theo code mẫu) vẫn tính lặp lại tổng các ước cho mỗi số, nhưng có một biến t tổng quát hóa hơn. Tuy nhiên, một cách cải tiến khác (không có trong code mẫu nhưng là insight tốt) là dùng Hash Map (unorderedmap) để lưu kết quả tổng các ước của các số đã tính. Nếu một số xuất hiện nhiều lần trong dãy, ta chỉ cần tính một lần. Tuy nhiên, do ai chỉ lên tới 10^4, giải pháp Sieve (Approach 2) thường nhanh và ổn định hơn do tránh được overhead của Hash Map và chi phí tính sqrt.

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

Bài học kinh nghiệm

• Bài toán này về bản chất là đếm số lượng số thỏa mãn tổng các ước (bao gồm chính nó) < 2*n và n != 1.
• Với giới hạn a_i <= 10^4 (hoặc 10^5), giải pháp Sieve (sàng) để precompute tổng các ước là tối ưu nhất về thời gian thực thi cho nhiều test case hoặc dãy số dài.
• Nếu chỉ có 1 test case với N lớn, việc tối ưu bằng cách loại bỏ các phép tính lặp lại (dùng mảng đánh dấu hoặc map) là cần thiết.

Lỗi thường gặp

• Quên kiểm tra n != 1: Số 1 có tổng các ước là 1, nhỏ hơn 2*1=2, nhưng theo định nghĩa bài toán thì 1 không phải là số gần hoàn hảo.
• Sai công thức tính tổng các ước: Khi duyệt đến số i là ước của n, cần cộng cả i và n/i vào tổng. Tuy nhiên, phải kiểm tra nếu i*i == n thì chỉ cộng 1 lần (tránh cộng trùng căn bậc 2).
• Lỗi tràn số biến tổng: Với các số lớn (dù bài này a_i nhỏ), tổng các ước có thể vượt quá giới hạn của int 32-bit nên dùng biến long long là an toàn.