Giúp đỡ bài tập trên VNOI

[Wipad]

Chào mọi người, nhờ mọi người giúp mình bài này với ạ Click here!

Sau khi loay xoay 1 hồi thì mình nhận thấy rằng: Chỉ cần xét các số chính phương vì chỉ có nó là có số ước số lẻ, và chỉ cần duyệt khoảng (sqrt(l) tới sqrt®)

Dù là thế nhưng 2 ngày rồi vẫn không làm được (bị TLE) nên nhờ mọi người giúp với ạ, cảm ơn mọi người. Cũng muốn tự làm lắm nhưng mà tư duy hạn hẹp quá

Nếu ai muốn xem code của mình thì đây

[tntxtnt]

hàm tìm số ước của 1 số n là \sigma_0(n) https://en.wikipedia.org/wiki/Divisor_function. Dãy các số này là https://oeis.org/A000005. Dãy có công thức là

If n is written as 2^z*3^y*5^x*7^w*11^v*... then 
a(n)=(z+1)*(y+1)*(x+1)*(w+1)*(v+1)*...

ở đây \sigma_0(n) = 7 thì vì 7 là số nguyên tố nên n chỉ được phép có 1 ước số nguyên tố thôi, và số mũ của ước này phải là 7 - 1 = 6, hay n có dạng p^6 với p nguyên tố :V

n lên tới 10^12 thì lấy căn bậc 6 của 10^12 là 10^2 là 100, tìm mọi số nguyên tố < 100 thì ra tất cả các số có dạng p^6 < 10^{12} thôi. Rồi đếm số lượng số L <= n <= R dễ rồi, tối đa có \pi(100) = 25 số thôi :V

---

edit: ơ đọc đề ko kĩ nó đòi tìm số có số các ước dương là số nguyên tố hả, vậy cũng có dạng p^{q-1} với p, q nguyên tố thôi :V

ví dụ cho 2 5 mà đáp án chỉ có 1 vậy là ko tính số nguyên tố hả? Đề gì tầm bậy, số nguyên tố có 2 ước số thì 2 cũng là nguyên tố mà. Đề dỏm. Nếu ko tính 2 ước thì có 3, 5, 7, 11, 13, v.v… ước thì dễ nữa, lập sàng tìm số nguyên tố < căn(10^12) = 10^6 rồi đếm là được.

[Wipad]

đây anh :))

[tntxtnt]

à à có chữ ko phải số nguyên tố nữa :V :V

vậy số đó phải có dạng p^{q-1} với p là số nguyên tố, q là số nguyên tố lẻ ví dụ như
2^{3-1}, 2^{5-1}, ..., 2^{37-1}
3^{3-1}, 3^{5-1}, ..., 3^{23-1}
5^{3-1}, 5^{5-1}, ..., 5^{17-1}
v.v…
tới 999983^{3-1} là hết cho R = 10^12 :V

[Wipad]

đội ơn anh, em làm được rồi.