Mình xin trình bày lời giải bàu này như sau:

Ta có nhận xét rằng: Hàm \(S(n)\) đề bài cho là hàm nhân tính. Nên giả sử phân tích thành nhân tử: \(N! = p_1^{\alpha_1}.p_2^{\alpha_2}...p_k^{\alpha_k}\implies (N!)^3 = p_1^{3\alpha_1}.p_2^{3\alpha_2}...p_k^{3\alpha_k}\)

Khi đó \(S(N!^3) = S(p_1^{3\alpha_1}).S(p_2^{3\alpha_2})...S(p_3^{3\alpha_k})\).

Và ta có thêm một nhận xét nữa là: \(S(p^\alpha)=1+p+...+p^{\alpha}\)

Do đó công việc còn lại của chúng ta là phần tích \(N!\) thành nhân tử và tính biểu thức trên là xong.

Bài toán phân tích \(N!\) chính là bài 1 và bài toàn tính \(S(p^\alpha)\) chính là bài 2

Như vậy là bài toán đã được giải quyết xong

Một điều cần lưu ý ở bài này để AC được task cuối đó là với \(n=4 * 10^7\). Để khai báo một mảng có kích thước \(4 * 10^7\) trong quá trình sàng nguyên tố. Ta phải khai báo chúng ở \(int\) (Vì nếu khai báo là \(long long\) thì sẽ bị runtime error đấy nhé).

Các bạn có thể tham khảo code tại đây