Subtask 1. ~B \le 10^3~

Đặt ~N = B - A~.

Duyệt ~i~ từ ~a~ tới ~b~. Sử dụng một vòng lặp nữa để đếm số ước. Nếu thỏa mãn thì tăng kết quả lên ~1~.

Độ phức tạp: ~O~ (~N^2~).

Subtask 2. ~B \le 10^6~

Sử dụng sàng tổng ước để đếm nhanh số ước.

Độ phức tạp: ~O~ (~N \times log~ ~N~).

Subtask 3. ~B \le 10^{18}~

Xét số ~i~, gọi ~i = p_1^{q_1} \times p_2^{q_2} \times ... \times p_k^{q_k}~, số ước của ~i~ là ~(q_1 + 1) \times (q_2 + 1) \times ... \times (q_k + 1)~.

Để số ước của ~i~ là lẻ thì mọi ~q_x + 1~ đều phải lẻ, hay ~q_x~ phải đều chẵn. Khi ~q_x~ đều chẵn thì ~i~ là số chính phương.

Vì vậy, bài toán chuyển về đếm số lượng số không là số chính phương trong ~[A, B]~. Ta sẽ đếm số lượng số không là số chính phương trong ~[1, B]~ (hay chính là ~B - \sqrt B~), rồi trừ đi số lượng số không là số chính phương trong ~[1, A - 1]~.

Độ phức tạp: ~O~ (~1~).