Nhắc nhở:

Khuyến khích mọi người nên tự tìm hiểu, suy nghĩ lời giải trước khi tham khảo

Nên đọc kỹ hướng dẫn trước khi tham khảo bài làm

Cách 1: đếm ước bằng cách duyệt

Với mỗi số $x$, ta sẽ thực hiện tính tổng số ước bằng cách bình thường.

> Chúng ta có thể tăng tốc độ duyệt bằng cách chỉ duyệt đến $\sqrt{x}$

Độ phức tạp: $O$($q * \sqrt{x}$)

Cách 2: đếm ước bằng cách phân tích thừa số nguyên tố

Dựa vào việc chỉ cần duyệt đến $\sqrt{n}$ như cách 1, ta có thể phân tích thừa số nguyên tố mà các ước nguyên tố của $x$ đều sẽ nhỏ hơn $\sqrt{x}$ (và trong trường hợp xấu nhất thì sẽ chỉ có 1 ước nguyên tố của $x$ là lớn hơn $\sqrt{x}$, các bạn có thể tự chứng minh phần này)

Do đó, ta sẽ tạo sàng nguyên tố từ 1 đến 31625 (vì 31625 sẽ là đủ để duyệt các số nguyên tố nhỏ hơn hoặc bằng $\sqrt{10^9}$, tức là $\sqrt{x}$ lớn nhất) . Rồi ta sẽ lưu các số nguyên tố vào 1 mảng để chúng ta duyệt và phân tích thừa số nguyên tố của $x$, đồng thời đếm ước của $x$ bằng công thức sau:

$res$ $=$ $(m_1 + 1) * (m_2 + 1) * … * (m_k + 1)$ (*)

Với $m_1, m_2, … m_k$ là số mũ của các thừa số nguyên tố của $x$

int demuoc(int n)
{
    //des để đánh dấu vị trí kết thúc việc duyệt, là khi đạt đến giá trị căn bậc 2 của n
    //v[] là mảng vector lưu các số nguyên tố từ 1 -> 31625
    int i,temp,res=1,d,des; 
    des=upper_bound(v.begin(),v.end(),sqrt(n))-v.begin();
    for(i=0;i<des;i++)
    {
        temp=v[i]; d=0; //d để đếm số mũ của ước nguyên tố khi phân tích
        if (n%temp==0) 
        {
            while (n%temp==0)
            {
                n/=temp; d++; //thực hiện phân tích thừa số nguyên tố
            }
        }
        res*=(d+1); //tính ước bằng công thức (*)
        if (n==1||temp>n) break; //kết thúc khi n đã hoàn thành việc phân tích thừa số nguyên tố
        //hoặc ko có thừa số nguyên tố nào mà n lớn hơn nữa
    }
    if (n!=1) res*=2; //trong trường hợp xấu nhất, nếu n có ước nguyên tố lớn hơn căn bậc 2 của n
    //thì số lượng ước của n sẽ đc nhân 2 theo công thức (*)
    return res;
}

Độ phức tạp: $O$($q * \sqrt{x}$)

(Do độ phức tạp của thuật toán bỏ qua các giá trị hằng số, nên so với cách 1 thì cách 2 trên thực tế sẽ nhanh hơn ~10 lần vì chúng ta chỉ cần duyệt dãy các số nguyên tố thay vì phải duyệt toàn bộ các giá trị từ 1 đến $\sqrt{n}$, và sẽ là đủ nhanh để AC bài này)

Bài giải:

> Giải thuật: phân tích thừa số nguyên tố (cải tiến bằng sàng nguyên tố)

> Độ phức tạp: $O$($q$ * $\sqrt{x}$)

> Ngôn ngữ lập trình: C++ 11

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=31625; int f[N]={};
vector<int> v;
void sieve(int n)
{
    int i,j,sqrtn=sqrt(n);
    for(i=2;i<=n;i++)
    {
        if (f[i]==0)
        {
            v.push_back(i); //lưu các giá trị số nguyên tố trong khi sàng
            if (i<=sqrtn)
            {
                for(j=i*i;j<=n;j+=i) f[j]=1;
            }
        }
    }
}
int demuoc(int n) 
{
    int i,temp,res=1,d,des;
    des=upper_bound(v.begin(),v.end(),sqrt(n))-v.begin();
    for(i=0;i<des;i++)
    {
        temp=v[i]; d=0;
        if (n%temp==0)
        {
            while (n%temp==0)
            {
                n/=temp; d++;
            }
        }
        res*=(d+1);
        if (n==1||temp>n) break;
    }
    if (n!=1) res*=2;
    return res;
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,x;
    sieve(N);
    cin>>n; while (n--)
    {
        cin>>x; cout<<demuoc(x)<<endl;
    }
}

Lưu ý: có thể có nhiều hơn một cách làm nên các bạn không nhất thiết phải làm theo lời giải