Tổng Hàm Nhân Tính
Xem PDF
Điểm:
2300
Thời gian:
1.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một hàm số nhân tính \(f(n)\) được xác định trên tập các số nguyên dương \(\mathbb{N}^*\). Hàm \(f(n)\) thỏa mãn tính chất \(f(n) = n \cdot \phi(n)\), trong đó \(\phi(n)\) là hàm phi Euler (số lượng các số nguyên dương \(k \le n\) sao cho \(\gcd(k, n) = 1\)).
Cho số nguyên dương \(N\). Hãy tính tổng sau:
\[S(N) = \sum_{i=1}^{N} f(i) \pmod{10^9 + 7}\]
Input
- Dòng duy nhất chứa một số nguyên dương \(N\) (\(1 \le N \le 10^{10}\)).
Output
- In ra một số nguyên duy nhất là giá trị của \(S(N) \pmod{10^9 + 7}\).
Example
Test 1
Input
4Output
17Note
Các giá trị \(f(i)\) với \(1 \le i \le 4\) là:
- \(f(1) = 1 \cdot \phi(1) = 1 \cdot 1 = 1\)
- \(f(2) = 2 \cdot \phi(2) = 2 \cdot 1 = 2\)
- \(f(3) = 3 \cdot \phi(3) = 3 \cdot 2 = 6\)
- \(f(4) = 4 \cdot \phi(4) = 4 \cdot 2 = 8\)
Tổng \(S(4) = 1 + 2 + 6 + 8 = 17\).
Scoring
- Subtask 1 (100% số điểm): \(1 \le N \le 10^{10}\).
Bình luận