Giá trị kỳ vọng
Đề bài
Mô tả
Cho một hoán vị của số nguyên dương đầu tiên, ta định nghĩa:
- là ước chung lớn nhất của phần tử đầu tiên của ().
- là số giá trị phân biệt trong dãy .
Ví dụ, với thì:
- ,
- ,
- ,
- ,
- ,
- .
Do đó .
Cho số nguyên , ta sinh ngẫu nhiên một hoán vị độ dài (mỗi hoán vị có cùng xác suất). Hãy tính kỳ vọng của .
Dữ liệu vào
Một dòng gồm một số nguyên .
Dữ liệu ra
In ra kỳ vọng của modulo .
Cụ thể, đặt . Có thể chứng minh rằng đáp án biểu diễn được dưới dạng phân số tối giản với , là các số nguyên và . Hãy in ra số nguyên bằng , nói cách khác, số nguyên thỏa mãn và .
Ràng buộc
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 | 500000005 | Hoán vị có , hoán vị có (dãy là ). Kỳ vọng là . |
| 3 | 666666673 | Hai hoán vị bắt đầu bằng có , bốn hoán vị còn lại có . Kỳ vọng là . |
Bình luận