Tổng hàm phi Euler trên đoạn

Buổi 57 — Sàng & Euler Totient Buổi 69-70 — Mock Tổng hợp Mathematics Number Theory
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Hàm phi Euler $\varphi(n)$ là số lượng số nguyên dương không vượt quá $n$ và nguyên tố cùng nhau với $n$. Cho $Q$ truy vấn, mỗi truy vấn gồm hai số nguyên $L, R$. Hãy tính $\sum_{i=L}^{R} \varphi(i)$.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $Q$.
  • $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L, R$.
Dữ liệu ra

In ra $Q$ dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Ví dụ
Input Output
3
1 5
3 6
10 10
10
10
4
Giới hạn

$1 \le Q \le 10^5$, $1 \le L \le R \le 10^6$.

Draft saved