Tổng số ước các ước
Xem PDF
Điểm:
500 (p)
Thời gian:
1.0s
Bộ nhớ:
1023M
Input:
bàn phím
Output:
màn hình
Hàm \(D[n]\) biểu thị số ước của một số nguyên \(n\). Ví dụ \(D[24]=8\) (Các ước của \(24\) là \(1, 2, 3, 4, 6, 8, 12, 24\)).
Hàm \(F[n]\) biểu thị tổng số ước các ước của \(n\). Ví dụ \(F[24]=D[1]+D[2]+D[3]+D[4]+D[6]+D[8]+D[12]+D[24]=30\)
Cho số tự nhiên \(n\), hãy tính \(F[n!]\), trong đó \(n!= 1 * 2 * 3 * ... * n\)
Input
- Input gồm nhiều dòng
- Mỗi dòng chứa số nguyên dương \(n(n \leq 10^6)\)
- Input kết thúc bởi số \(0\)
Output
- Gồm nhiều dòng, mỗi dòng tương ứng với mỗi test
- Mỗi dòng chứa phần dư \(F[n!]\) cho \(10^7 +7\)
Example
Test 1
Input
4
5
1
0 Output
30
90
1
Bình luận
orz
bài toán rất hay !
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Thấy nhiều bạn thảo luận sôi nổi bên nhóm chat về bài này, mình xin chia sẻ lời giải bài này như sau:
Gọi \(\tau(d)\) là số ước của \(d\) với \(d\) là số nguyên dương. Ví dụ \(\tau(5)=2\) (Vì \(5\) có \(2\) ước là \(1\) và \(5\)).
Khi đó theo đề ta có: \(F(n)=\sum\limits_{d|n}\tau(d)\).
Ta có những tính chất quan trọng sau: Nếu \(f\) là \(1\) hàm nhân tính thì hàm xác định bởi công thức \(F(n)=\sum\limits_{d|n}f(d)\) cũng là hàm nhân tính. (Các bạn có thể tham khảo tại \(\href{https://vnoi.info/wiki/algo/math/multiplicative-function}{VNOI}\))
Áp dụng tính chất quan trọng này vào bài toán, ta có: Vì \(\tau(d)\) là hàm nhân tính, nên từ đây ta suy ra được \(F(n)\) cũng là hàm nhân tính.
Khi đó \(F(n)=F(p_1^{\alpha_1})F(p_2^{\alpha_{2}})...F(p_k^{\alpha_{k}})\) (với \(n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k},p_i\in \mathbb{P}\forall i=\overline{1,k}\), trong đó \(\mathbb{P}\) là tập hợp các số nguyên tố)
Việc còn lại vô cùng đơn giản đó là ta chỉ tính \(F(p_i^{\alpha_i})\forall i=\overline{1,k}\).
Để tính được \(F(p_i^{\alpha_i})\), ta cần chú ý một tính chất quan trọng của hàm \(\tau(d)\) đó là : Nếu \(d=p^{\alpha}(p\in \mathbb{P})\) thì \(\tau(p^{\alpha})=\alpha+1\)
Khi đó ta có: \(F(p_i^{\alpha_i})=\sum\limits_{d|p_i^{\alpha_i}}\tau(d)=\tau(1)+\tau(p_i^{1})+...+\tau(p_i^{\alpha_i})=1+2+...+(\alpha_i+1)=\frac{(\alpha_i+1)(\alpha_i+2)}{2}\)
Từ đây ta suy ra được: \(F(n)=\prod\limits_{i=1}^{k}\frac{(\alpha_i+1)(\alpha_i+2)}{2}\) với \(n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k},p_i\in \mathbb{P}\forall i=\overline{1,k}\)
Đến đây công việc còn lại đơn giản đó là phân tích \(n\) thành nhân tử và tính biểu thức trên.
Tiếp theo là đến phần code !
Ở đây đề bài lại bắt chúng ta tính \(F(n)\) với \(n=N\text{!}\), nên ở đây sẽ có đôi chút kĩ thuật, các bạn đón xem tiếp nhé!
Đầu tiên ta có một tính chất khá hay như sau: Nếu \(p\) là số nguyên tố, thì số mũ của \(p\) trong \(N\text{!}\) đó là: \([\frac{N}{p}]+[\frac{N}{p^{2}}]+...+[\frac{N}{p^{k}}]\) với \(N < p^{k+1}\) (Công thức Lagrange)
Tiếp theo chúng ta cần tạo trước mảng chứa các số nguyên tố nhỏ hơn \(10^6\), làm tiền đề để tính các \(\alpha_i\), các bạn có thể tham khảo code tại đây !
Và công việc còn lại chỉ là đi tính từng \(\alpha_i\), cái này xin dành cho bạn đọc (Cũng đơn giản thôi !)
Và cuối cùng là đi tính \(F(n)\text{ % } mod\) là xong. Như vậy là bài toán đã được giải quyết
Dưới đây là code của mình, các bạn có thể tham khảo tại \(\href{https://ideone.com/DB015Z}{đây}\)
P/s: Nếu có gì sai hoặc khó hiểu hoặc thắc mắc, các bạn cứ comment nhé !