Solution 1: Brute-force (Ngây thơ)

• Ta sẽ \(\text{for}\) từ \(1\) đến \(N\) để tính tổng số ước.
• Như vậy ta có độ phức tạp:
  • Thời gian: \(O(q\times N)\) \(\rightarrow\) \(\color{red}\text{Không tối ưu}\)
  • Không gian: \(O(1)\)

Solution 2: Brute-force (Khôn hơn)

• Ta có thể \(\text{for}\) từ \(1\) đến \(\lfloor \sqrt{N} \rfloor\) để tính tổng số ước.
• Như vậy ta có độ phức tạp:
  • Thời gian: \(O(q\times \lfloor \sqrt{N} \rfloor)\) \(\rightarrow\) \(\color{red}\text{Không tối ưu}\)
  • Không gian: \(O(1)\)

Solution 3: Tiền xử lý

• Vì \(1\le n\le 10^6\) nên ta dùng một mảng \(A\) để có giá trị \(i\) tương ứng với \(A_i\) là tổng số ước của \(i\) đã được \(\text{mod}\) \(10^9+7\).
• Như vậy ta có độ phức tạp:
  • Thời gian: \(O(10^6 \times log_2(10^6) + q)\) \(\rightarrow\) \(\color{green}\text{Tối ưu}\)
  • Không gian: \(O(N)\)

Solution 4: Rãnh quá sinh nông nỗi

• Ta sẽ dùng thuật toán SPF để tìm số nguyên tố gần với giá trị \(k\) trong quá trình phân tích thừa số nguyên tố.
• Ta đồng thời lưu vào map để có \(\text{value}\) là cơ số và \(\text{key}\) là số mũ.
• Ta sẽ có công thức như sau để tính tổng: \(\frac{{a_1}^{p_1+1}-1}{{a_1}-1}\times \frac{{a_2}^{p_2+1}-1}{{a_2}-1}\times \frac{{a_3}^{p_3+1}-1}{{a_3}-1}\times \cdots \times \frac{{a_n}^{p_n+1}-1}{{a_n}-1}\).
• Chú ý khi chia nên nghịch đảo \(\text{Modulo}\) để tránh sai sót.
• Bạn hãy nhớ viết thêm hàm Lũy thừa nhị phân để tính các phép toán mũ nhanh nhé!