Lời giải

Hai đại lượng đầu là các hàm nhân tính quen thuộc:

• Số ước: ~d(m) = \prod (x_i + 1)~
• Tổng các ước: ~\sigma(m) = \prod \dfrac{p_i^{x_i + 1} - 1}{p_i - 1}~ (dùng nghịch đảo modulo cho phép chia)

Tích các ước khó hơn: ghép mỗi ước ~e~ với ~m / e~ ta được ~\prod_{e \mid m} e = m^{d(m)/2}~.

Vấn đề là ~d(m)~ khổng lồ nên không thể lấy ~d(m)/2~ trực tiếp, và ~d(m)~ có thể là số lẻ — đúng khi ~m~ là số chính phương, tức là khi mọi ~x_i~ đều chẵn. Hãy xử lý hai trường hợp riêng:

• Nếu tồn tại ~x_j~ lẻ thì ~x_j + 1~ chẵn: hãy chia đôi riêng thừa số đó rồi nhân phần còn lại, tất cả theo modulo ~10^9 + 6~ (định lý Fermat), sau đó tính ~m^{\text{số mũ đó}}~.
• Nếu mọi ~x_i~ đều chẵn thì ~\sqrt{m} = \prod p_i^{x_i/2}~ là số nguyên, và tích các ước bằng ~(\sqrt{m})^{d(m)}~.

Lưu ý số mũ phải lấy theo modulo ~10^9 + 6~ chứ không phải ~10^9 + 7~.