• 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 !

const ll  N = 1000000;
ll  lp[N+1];
vector<ll > pr;
void solve(){
for (ll  i=2; i<=N; ++i) {
    if (lp[i] == 0) {
        lp[i] = i;
        pr.push_back (i);
    }
    for (ll  j=0; j<(ll )pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
        lp[i * pr[j]] = pr[j];
}
}

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é !