# 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ố](https://wiki.vnoi.info/translate/he/Number-Theory-2) 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)$ [(*)](https://www.mathvn.com/2020/01/cong-thuc-tinh-so-uoc-so-nguyen-duong.html)
Với $m_1, m_2, ... m_k$ là số mũ của các thừa số nguyên tố của $x$
```cpp
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**
```cpp
#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
giavinh650
Created at
4 likes