# 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: Duyệt (cơ bản)
Với mỗi truy vấn $l, r$, chúng ta sẽ duyệt các giá trị từ $l$ đến $r$, rồi đếm ước của các số và cộng vào. Sau đó in ra màn hình.
> Các bạn có thể duyệt đến $\sqrt{n}$ để tối ưu hóa thuật toán này.
Độ phức tạp: $O$($q * (\sqrt{n})^3$)
### Cách 2: Cải tiến sàng nguyên tố thành sàng đếm ước
Áp dụng thuật toán trên, nhưng thay vì duyệt từng giá trị để đếm ước thì ta sẽ cải tiến sàng nguyên tố
thành sàng đếm ước để tăng tốc độ duyệt: duyệt $i$ từ 1 đến $r$, với mỗi lần duyệt, chúng ta sẽ cộng 1 vào mảng có các giá trị là bội của số đó
(tức với mỗi giá trị $i$, ta sẽ tăng số lượng ước của các số là bội của $i$).
Sau khi sàng thì chúng ta sẽ có một mảng lưu số lượng ước của các số, và từ đó giúp tiết kiệm thời gian đếm ước
(từ $O$($\sqrt{n}$) xuống $O$($1$))
```
void sieve(int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j+=i) f[j]++;
}
}
```
Độ phức tạp: $O$($q * n$)
### Cách 3: Sàng đếm ước + Mảng cộng dồn
**Các bạn có thể tham khảo mảng cộng dồn tại các trang này:**
[Mảng cộng dồn (VNOI Wiki)](https://wiki.vnoi.info/algo/data-structures/prefix-sum-and-difference-array.md)
[Prefix Sum (USACO Guide)](https://usaco.guide/silver/prefix-sums)
Chúng ta vẫn sử dụng thuật toán từ cách 2, nhưng thay vì phải duyệt từ $l$ đến $r$ rồi tính tổng, chúng ta có thể lưu các giá trị đó vào
mảng cộng dồn, sau đó với mỗi truy vấn $l, r$, chúng ta chỉ việc in ra màn hình (và thời gian duyệt các truy vấn
$(l, r)$ sẽ không đáng kể nữa).
Độ phức tạp: $O$($n$ * $\log(n)$) (do sàng đếm ước tốn $O$($n$ * $\log(n)$))
## Bài giải:
> Giải thuật: sàng đếm ước + mảng cộng dồn
> Độ phức tạp: $O$($n$ * $\log(n)$)
> 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=1e6+10; int f[N]={},tong[N]={};
void sieve(int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j+=i) f[j]++;
tong[i]=tong[i-1]+f[i];
}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
sieve(N);
int l,r,q;
cin>>q; while (q--)
{
cin>>l>>r;
cout<<tong[r]-tong[l-1]<<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
2 likes