Bình luận

• 
  

  0

  

  pt48583994  đã bình luận lúc 12, Tháng 6, 2025, 3:17 ← sửa 3 →

  Comment này spoil thuật

  Xét các giá trị từ 2 đến 7 (hoặc 5 nếu số không có dạng ~4^{m}*(8*k+7)~)

  Tách các số (từ 2 đến 7) thành 2 phần (hoặc 3 phần) và for các phần bé nhất (có số mũ lớn nhất). Phần có số mũ bé nhất sẽ là 2 hoặc 3 và có thể check trong ~O(1)~.

  Nếu bạn đã làm đến đây rồi thì ĐPT sẽ là ~O(N^{5/6})~, đủ để qua bài.

  Tuy nhiên có thể tối ưu check cho 4 xuống ~O(N^{1/4+\epsilon})~ để tối ưu check cho 7 xuống ~O(N^{7/12+\epsilon})~.