Hàm Euler φ(n) đếm số nguyên trong [1,n] nguyên tố cùng nhau với n. Đây là một hàm nhân tính.
Cho số nguyên n, hãy tính tổng Φ(n)=∑i=1nφ(i)mod(109+7).
Sử dụng sàng để tính toàn bộ φ(1..n) rồi cộng dồn.
Ví dụ: φ(1)=1,φ(2)=1,φ(3)=2,φ(4)=2, nên Φ(4)=6.
Một dòng chứa số nguyên n.
0≤n≤2⋅106.
In ra Φ(n)mod(109+7).
Ví dụ:
Đầu vào:
4
Đầu ra:
6
Giải thích:
Đang tải editor...